Welcome to Subscribe On Youtube

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

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.

  • 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;
    }
}


  • 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;
    }
};


  • 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


  • 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
}


  • 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('');
}

All Problems

All Solutions