Leetcode 1370 题 上升下降字符串

题目描述

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

1. 从 s 中选出最小的字符，将它接在结果字符串的后面。
2. 从 s 剩余字符中选出最小的字符，且该字符比上一个添加的字符大，将它接在结果字符串后面。
3. 重复步骤 2 ，直到你没法从 s 中选择字符
4. 从 s 中选出最大的字符，将它接在结果字符串的后面。
5. 从 s 剩余字符中选出最大的字符，且该字符比上一个添加的字符小，将它接在结果字符串后面。
6. 重复步骤 5 ，直到你没法从 s 中选择字符。
7. 重复步骤 1 到 6 ，直到 s 中所有字符都已经被选过。

示例：
输入：s = "aaaabbbbcccc"
输出："abccbaabccba"

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

思路分析

这道题的题目描述很长，实际上就做两件事，搜索字符，按从小到大排序以及按从大到小排序。拿上面所给出的例子讲解，先从小到大查找到 abc，再从大到小查到 cba，依次从大到小和从小到大查询，直到所有字符都被使用，最后将查到的结果拼接。

题目中给出 s 只包含小写字母，因此，我们可以提供一个大小为 26 的数组，用来保存每个字母出现的次数。

从小到大以及从大到小遍历数组，找到出现次数大于 0 的字母即可。这里的细节部分就不做过多描述，详细可以查看以下代码。

代码描述

使用 Java 进行代码描述：

class Solution {
    public String sortString(String s) {
        int [] count = new int[26]; // 用于保存字母出现的次数
        int length = s.length();

        for (int i = 0; i < length; i++) { // 统计字母出现的次数
            count[s.charAt(i) - 'a']++;
        }

        StringBuffer sb = new StringBuffer();
        while (sb.length() < length) {
            for (int i = 0; i < 26; i++) { // 正序查找
                if (count[i] > 0) {
                    sb.append((char) (i + 'a'));
                    count[i]--;
                }
            }

            for (int i = 25; i >= 0; i--) { // 倒序查找
                if (count[i] > 0) {
                    sb.append((char) (i + 'a'));
                    count[i]--;
                }
            }
        }
        return sb.toString();
    }
}

欢迎关注

技术公众号：小猿君的算法笔记

订阅号.png