上升下降字符串

难度: 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"

示例 3：

输入：s = "leetcode"
输出："cdelotee"

示例 4：

输入：s = "ggggggg"
输出："ggggggg"

示例 5：

输入：s = "spo"
输出："ops"

提示：

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

Submission

运行时间: 36 ms

内存: 16.5 MB

class Solution:
    def sortString(self, s: str) -> str:
        cnt = Counter(s)
        cs = ascii_lowercase + ascii_lowercase[::-1]
        ans = []
        while len(ans) < len(s):
            for c in cs:
                if cnt[c]:
                    ans.append(c)
                    cnt[c] -= 1
        return ''.join(ans)

Explain

题解采用了贪心算法的思想，通过统计字符串s中每个字符的出现频次，并用一个计数器cnt来管理。接着，定义一个字符序列cs，它包含了所有小写字母按顺序排列，后接所有小写字母的逆序。这样，遍历cs可以模拟题目中描述的从小到大再从大到小的字符选择过程。循环遍历cs，每次尝试将cs中的字符加入到结果ans中，如果该字符在cnt中的计数大于0，说明它仍然可用，将其加入结果字符串并减少计数。这一过程一直持续到构建的字符串长度等于原字符串长度为止。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution: 
    def sortString(self, s: str) -> str: 
        cnt = Counter(s)  # 使用Counter统计每个字符的出现次数 
        cs = ascii_lowercase + ascii_lowercase[::-1]  # 创建正序和逆序的小写字母字符串 
        ans = []  # 初始化结果列表 
        while len(ans) < len(s):  # 直到结果字符串长度等于原字符串长度 
            for c in cs:  # 遍历字符序列cs 
                if cnt[c]:  # 如果字符c在计数器中的计数大于0 
                    ans.append(c)  # 将字符c添加到结果列表 
                    cnt[c] -= 1  # 减少字符c的计数 
        return ''.join(ans)  # 将列表转换为字符串后返回

Explore

在题解中，贪心算法的思想主要体现在每次遍历字符序列cs时，总是尽可能地选择当前可用的字符加入到结果字符串中。这种方法选择每个步骤的局部最优解（即当前可用的最小或最大字符），以期望最终构成全局最优的字符串顺序。这种从局部最优推向全局最优的策略是贪心算法的典型特征。

选择使用正序和逆序两次遍历的方式是为了模拟题目要求的'上升下降字符串'过程，即先从'a'到'z'选择可用的最小字符，然后从'z'到'a'选择可用的最大字符。这种方式可以确保每一轮从小到大和从大到小的字符选择是完整的，与单次遍历相比，能够更好地遵循题目的规则，同时也使得构建的字符串更加有序和符合要求。

尽管字符频次降为0后，在后续的遍历中仍然会检查这个字符，但是这种检查的开销非常小，因为它仅涉及到一个哈希表的查询操作，其时间复杂度为O(1)。尽管这会增加一些运算，但对总体算法效率的影响是微小的，因为这保持了算法的结构简单和清晰。

当输入字符串中有大量重复字符时，算法仍然能够有效运行，因为每个字符被计数并根据题目规则逐一添加到结果字符串中。然而，如果重复字符非常多，每次遍历字符序列cs时，大部分字符可能都不可用，这可能会导致算法多次无效遍历，从而在某种程度上降低效率。尽管如此，由于cs的长度固定为52（26个小写字母的正序和逆序），这种效率下降通常是可管理的。