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.

 

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

Thinking

We must reverse exactly one prefix or suffix, so there are only \(n\) choices of \(k\). Enumerating each \(k\), building both candidates, and taking the lexicographically smallest string is enough.

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