Skip to content

3722. Lexicographically Smallest String After Reverse

Description

You are given a string s of length n consisting of lowercase English letters.

You must perform exactly one operation by choosing any integer k such that 1 <= k <= n and either:

  • reverse the first k characters of s, or
  • reverse the last k characters of s.

Return the lexicographically smallest string that can be obtained after exactly one such operation.

A string a is lexicographically smaller than a string b if, at the first position where they differ, a has a letter that appears earlier in the alphabet than the corresponding letter in b. If the first min(a.length, b.length) characters are the same, then the shorter string is considered lexicographically smaller.

 

Example 1:

Input: s = "dcab"

Output: "acdb"

Explanation:

  • Choose k = 3, reverse the first 3 characters.
  • Reverse "dca" to "acd", resulting string s = "acdb", which is the lexicographically smallest string achievable.

Example 2:

Input: s = "abba"

Output: "aabb"

Explanation:

  • Choose k = 3, reverse the last 3 characters.
  • Reverse "bba" to "abb", so the resulting string is "aabb", which is the lexicographically smallest string achievable.

Example 3:

Input: s = "zxy"

Output: "xzy"

Explanation:

  • Choose k = 2, reverse the first 2 characters.
  • Reverse "zx" to "xz", so the resulting string is "xzy", which is the lexicographically smallest string achievable.

 

Constraints:

  • 1 <= n == s.length <= 1000
  • s consists of lowercase English letters.

Solutions

Solution 1: Enumeration

We can enumerate all possible values of \(k\) (\(1 \leq k \leq n\)). For each \(k\), we compute the string obtained by reversing the first \(k\) characters and the string obtained by reversing the last \(k\) characters, then take the lexicographically smallest string among them as the final answer.

The time complexity is \(O(n^2)\) and the space complexity is \(O(n)\), where \(n\) is the length of the string.

1
2
3
4
5
6
7
8
class Solution:
    def lexSmallest(self, s: str) -> str:
        ans = s
        for k in range(1, len(s) + 1):
            t1 = s[:k][::-1] + s[k:]
            t2 = s[:-k] + s[-k:][::-1]
            ans = min(ans, t1, t2)
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
    public String lexSmallest(String s) {
        String ans = s;
        int n = s.length();
        for (int k = 1; k <= n; ++k) {
            String t1 = new StringBuilder(s.substring(0, k)).reverse().toString() + s.substring(k);
            String t2 = s.substring(0, n - k)
                + new StringBuilder(s.substring(n - k)).reverse().toString();
            if (t1.compareTo(ans) < 0) {
                ans = t1;
            }
            if (t2.compareTo(ans) < 0) {
                ans = t2;
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    string lexSmallest(string s) {
        string ans = s;
        int n = s.size();
        for (int k = 1; k <= n; ++k) {
            string t1 = s.substr(0, k);
            reverse(t1.begin(), t1.end());
            t1 += s.substr(k);

            string t2 = s.substr(0, n - k);
            string suffix = s.substr(n - k);
            reverse(suffix.begin(), suffix.end());
            t2 += suffix;

            ans = min({ans, t1, t2});
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
func lexSmallest(s string) string {
    ans := s
    n := len(s)
    for k := 1; k <= n; k++ {
        t1r := []rune(s[:k])
        slices.Reverse(t1r)
        t1 := string(t1r) + s[k:]

        t2r := []rune(s[n-k:])
        slices.Reverse(t2r)
        t2 := s[:n-k] + string(t2r)

        ans = min(ans, t1, t2)
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
function lexSmallest(s: string): string {
    let ans = s;
    const n = s.length;
    for (let k = 1; k <= n; ++k) {
        const t1 = reverse(s.slice(0, k)) + s.slice(k);
        const t2 = s.slice(0, n - k) + reverse(s.slice(n - k));
        ans = [ans, t1, t2].sort()[0];
    }
    return ans;
}

function reverse(s: string): string {
    return s.split('').reverse().join('');
}

Comments