题目

Given a string s. You should re-order the string using the following algorithm:

Pick the smallest character from s and append it to the result.
Pick the smallest character from s which is greater than the last appended character to the result and append it.
Repeat step 2 until you cannot pick more characters.
Pick the largest character from s and append it to the result.
Pick the largest character from s which is smaller than the last appended character to the result and append it.
Repeat step 5 until you cannot pick more characters.
Repeat the steps from 1 to 6 until you pick all characters from s.

In each step, If the smallest or the largest character appears more than once you can choose any occurrence and append it to the result.

Return the result string after sorting s with this algorithm.

Example 1:

Input: s = “aaaabbbbcccc”
Output: “abccbaabccba”
Explanation: After steps 1, 2 and 3 of the first iteration, result = “abc”
After steps 4, 5 and 6 of the first iteration, result = “abccba”
First iteration is done. Now s = “aabbcc” and we go back to step 1
After steps 1, 2 and 3 of the second iteration, result = “abccbaabc”
After steps 4, 5 and 6 of the second iteration, result = “abccbaabccba”

Example 2:

Input: s = “rat”
Output: “art”
Explanation: The word “rat” becomes “art” after re-ordering it with the mentioned algorithm.

Example 3:

Input: s = “leetcode”
Output: “cdelotee”

Example 4:

Input: s = “ggggggg”
Output: “ggggggg”

Example 5:

Input: s = “spo”
Output: “ops”

Constraints:

1 <= s.length <= 500
s contains only lower-case English letters.

分析

题意：给定一个字符串，每次从中挑选比上一个小的字符加入结果集（第一次为最小），直到没有最小的为止；然后再每次从中挑选比上一个大的字符加入结果集（第一次为最大），直到没有最大的为止。

思路：一开始的想法是对字符串排序，然而，最多出现26个字母，而这26个字母的大小都是已知的。因此，可以这么做.

1.构造一个26位的数组，数组下标表示对应字母，如a=0，z=25。
2.遍历字符串，每出现一个字母，就让数组对应位置++；
3.正向遍历数组，将字母加到结果集，并让该位置--；
4.反向遍历数组，将字母加到结果集，并让该位置--；
重复3-4，直到数组中的所有值为0.

解答

class Solution {
    public String sortString(String s) {
        StringBuilder res = new StringBuilder();
        int[] tmp = new int[26];
        for(char c:s.toCharArray()){
            tmp[c-'a']++;
        }
        while(res.length()<s.length()){
            for(int i=0;i<26;++i){
                if(tmp[i]!=0){
                    res.append((char)(i+'a'));
                    tmp[i]--;
                }
            }
            for(int i=25;i>=0;--i){
                if(tmp[i]!=0){
                    res.append((char)(i+'a'));
                    tmp[i]--;
                }
            }
        }
        return res.toString();
    }
}