1370. 递增递减字符串

Easy

题目描述

给你一个字符串 s ，请你根据下面的算法重新构造字符串：

从 s 中选出最小的字符，将它添加到结果中。
从 s 中选出最小的字符，且该字符比上一个添加的字符大，将它添加到结果中。
重复步骤 2 ，直到你没法再从 s 中选择字符。
从 s 中选出最大的字符，将它添加到结果中。
从 s 中选出最大的字符，且该字符比上一个添加的字符小，将它添加到结果中。
重复步骤 5 ，直到你没法再从 s 中选择字符。
重复步骤 1 到 6 ，直到从 s 中选出了所有的字符。

如果最小或者最大字符不止一个，你可以选择其中任意一个，并将其添加到结果中。

请你返回将 s 中字符重新排序后的 结果字符串。

示例 1：

输入：s = "aaaabbbbcccc"
输出："abccbaabccba"
解释：第一轮的步骤 1，2，3 后，结果字符串为 result = "abc"
第一轮的步骤 4，5，6 后，结果字符串为 result = "abccba"
第一轮结束，现在 s = "aabbcc" ，我们再次回到步骤 1
第二轮的步骤 1，2，3 后，结果字符串为 result = "abccbaabc"
第二轮的步骤 4，5，6 后，结果字符串为 result = "abccbaabccba"

示例 2：

输入：s = "rat"
输出："art"
解释：单词 "rat" 在上述算法重排序以后变成 "art"

提示：

1 <= s.length <= 500
s 只包含小写英文字母。

解题思路

这道题的核心思想是模拟题目描述的算法流程。我们需要交替进行两个过程：

递增过程：从最小字符开始，依次选择比前一个字符大的最小字符
递减过程：从最大字符开始，依次选择比前一个字符小的最大字符

解题思路：

首先统计每个字符的出现次数，使用频率数组或哈希表。然后重复执行以下步骤直到所有字符都被使用：

递增扫描：从 ‘a’ 到 ‘z’ 遍历，如果某个字符还有剩余（频次 > 0），就将其添加到结果中，并将频次减1
递减扫描：从 ‘z’ 到 ‘a’ 遍历，如果某个字符还有剩余，就将其添加到结果中，并将频次减1

这样的好处是：

递增扫描保证了字符是按升序添加的
递减扫描保证了字符是按降序添加的
通过频次控制确保每个字符恰好被使用原有的次数

时间复杂度为 O(n)，其中 n 是字符串长度。虽然有嵌套循环，但每个字符只会被访问常数次（最多26次）。

推荐解法： 使用频率数组的模拟法，简洁高效。

代码实现

class Solution {
public:
    string sortString(string s) {
        vector<int> count(26, 0);
        for (char c : s) {
            count[c - 'a']++;
        }
        
        string result;
        while (result.length() < s.length()) {
            // 递增：从 a 到 z
            for (int i = 0; i < 26; i++) {
                if (count[i] > 0) {
                    result += (char)('a' + i);
                    count[i]--;
                }
            }
            // 递减：从 z 到 a
            for (int i = 25; i >= 0; i--) {
                if (count[i] > 0) {
                    result += (char)('a' + i);
                    count[i]--;
                }
            }
        }
        
        return result;
    }
};

class Solution:
    def sortString(self, s: str) -> str:
        count = [0] * 26
        for c in s:
            count[ord(c) - ord('a')] += 1
        
        result = []
        while len(result) < len(s):
            # 递增：从 a 到 z
            for i in range(26):
                if count[i] > 0:
                    result.append(chr(ord('a') + i))
                    count[i] -= 1
            # 递减：从 z 到 a
            for i in range(25, -1, -1):
                if count[i] > 0:
                    result.append(chr(ord('a') + i))
                    count[i] -= 1
        
        return ''.join(result)

public class Solution {
    public string SortString(string s) {
        int[] count = new int[26];
        foreach (char c in s) {
            count[c - 'a']++;
        }
        
        StringBuilder result = new StringBuilder();
        while (result.Length < s.Length) {
            // 递增：从 a 到 z
            for (int i = 0; i < 26; i++) {
                if (count[i] > 0) {
                    result.Append((char)('a' + i));
                    count[i]--;
                }
            }
            // 递减：从 z 到 a
            for (int i = 25; i >= 0; i--) {
                if (count[i] > 0) {
                    result.Append((char)('a' + i));
                    count[i]--;
                }
            }
        }
        
        return result.ToString();
    }
}

var sortString = function(s) {
    const count = new Array(26).fill(0);
    for (let c of s) {
        count[c.charCodeAt(0) - 97]++;
    }
    
    let result = "";
    while (result.length < s.length) {
        // 递增：从 a 到 z
        for (let i = 0; i < 26; i++) {
            if (count[i] > 0) {
                result += String.fromCharCode(97 + i);
                count[i]--;
            }
        }
        // 递减：从 z 到 a
        for (let i = 25; i >= 0; i--) {
            if (count[i] > 0) {
                result += String.fromCharCode(97 + i);
                count[i]--;
            }
        }
    }
    
    return result;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型	分析
时间复杂度	O(n) - 每个字符最多被访问常数次，总体为线性时间
空间复杂度	O(1) - 只使用固定大小的频率数组（26个元素）

题目描述#

解题思路#

代码实现#

复杂度分析#

题目描述

解题思路

代码实现

复杂度分析