【LeetCode】1370. Increasing Decreasing String

Description

You are given a string s. Reorder 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.

Constraints:

1 <= s.length <= 500
s consists of only lowercase English letters.

給予一個字串 s，使用下面的演算法重新排序：

1. 從 s 拿一個最小的字元加到 result
2. 從 s 拿一個大於上一個加入的的字元的最小的字元加到 result
3. 重複步驟 2 直到不能再拿更多字元
4. 從 s 拿一個最大的字元加到 result
5. 從 s 拿一個小於上一個加入的的字元的最大的字元加到 result
6. 重複步驟 5 直到不能再拿更多字元
7. 重複 1 ~ 6 直到 s 的所有字元都被拿過

回傳 result，也就是經過演算法排序過的 s

限制：

1 <= s.length <= 500
s 只會包含小寫英文字母

Example:

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.

Solution

• 就照著題目刻完所有要求
  • 不是很好的題目，可能看懂題目比較困難
• 先排序字串 s，降低演算法的複雜度
• 利用 C++ STL 中的 string 和 algorthm lib 可以輕鬆完成

Code

class Solution {
public:
    string sortString(string s) {
        string result(s);
        int count = 0;
        char last;
        sort(s.begin(), s.end());
        while(!s.empty())
        {
            // alg 1
            last = s[0];
            result[count++] = last;
            s.erase(s.begin());
            // alg 2, 3
            for(int i = 0; i < s.size(); i++)
            {
                if(last != s[i])
                {
                    last = s[i];
                    result[count++] = last;
                    s.erase(s.begin() + i);
                    i--;
                }
            }

            if(s.empty())
                break;

            // alg 4
            last = s.back();
            result[count++] = last;
            s.erase(s.end() - 1);

            // alg 5, 6
            for(int i = s.size() - 1; i >= 0; i--)
            {
                if(last != s[i])
                {
                    last = s[i];
                    result[count++] = last;
                    s.erase(s.begin() + i);
                }
            }
        }
        return result;
    }
};

tags: LeetCode C++