3722. 反转后字典序最小的字符串

题目描述

给你一个由小写英文字母组成的、长度为 n 的字符串 s。

你必须执行恰好一次操作：选择一个整数 k，满足 1 <= k <= n，然后执行以下两个选项之一：

反转 s 的前 k 个字符，或
反转 s 的后 k 个字符。

返回在恰好执行一次此类操作后可以获得的 字典序最小 的字符串。

如果字符串 a 和字符串 b 在第一个不同的位置上，a 中的字母在字母表中比 b 中对应的字母出现得更早，则称字符串 a 字典序小于 字符串 b。如果前 min(a.length, b.length) 个字符都相同，则较短的字符串字典序较小。

示例 1:

输入: s = "dcab"

输出: "acdb"

解释:

选择 k = 3，反转前 3 个字符。
将 "dca" 反转为 "acd"，得到的字符串 s = "acdb"，这是可获得的字典序最小的字符串。

示例 2:

输入: s = "abba"

输出: "aabb"

解释:

选择 k = 3，反转后 3 个字符。
将 "bba" 反转为 "abb"，得到的字符串是 "aabb"，这是可获得的字典序最小的字符串。

示例 3:

输入: s = "zxy"

输出: "xzy"

解释:

选择 k = 2，反转前 2 个字符。
将 "zx" 反转为 "xz"，得到的字符串是 "xzy"，这是可获得的字典序最小的字符串。

提示:

1 <= n == s.length <= 1000
s 由小写英文字母组成。

解法

方法一：枚举

我们可以枚举所有可能的 \(k\) 值（\(1 \leq k \leq n\)），对于每个 \(k\)，我们计算反转前 \(k\) 个字符和反转后 \(k\) 个字符所得到的字符串，然后取其中字典序最小的字符串作为最终答案。

时间复杂度 \(O(n^2)\)，空间复杂度 \(O(n)\)。其中 \(n\) 是字符串的长度。

Python3JavaC++GoTypeScript

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

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

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

3722. 反转后字典序最小的字符串

题目描述

解法

方法一：枚举

评论