4073. Lexicographically Smallest String After Reverse¶

4073. Lexicographically Smallest String After Reverse

Medium

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:

Example 2:

Example 3:

Constraints:

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

Solution¶

class Solution {
    public String lexSmallest(String s) {
        int n = s.length();
        ArrayList<String> res = new ArrayList<>();
        for (int k = 1; k <= n; k++) {
            StringBuilder first = new StringBuilder(s.substring(0, k));
            String op1 = first.reverse().toString() + s.substring(k, n);

            StringBuilder second = new StringBuilder(s.substring(n - k, n));
            String op2 = s.substring(0, n - k) + second.reverse().toString();

            res.add(op1); res.add(op2);
        }
        Collections.sort(res);
        return res.get(0);
    }
}

Complexity Analysis¶

• Time Complexity: O(?)
• Space Complexity: O(?)

Explanation¶

[Add detailed explanation here]