Increasing and Decreasing String

You are given a string s and need to reconstruct the string based on the following algorithm:

  • Select the smallest character from s and append it to the end of the result string.
  • Select the smallest character from the remaining characters in s that is greater than the last added character and append it to the end of the result string.
  • Repeat step 2 until you can no longer select a character from s.
  • Select the largest character from s and append it to the end of the result string.
  • Select the largest character from the remaining characters in s that is smaller than the last added character and append it to the end of the result string.
  • Repeat step 5 until you can no longer select a character from s.
  • Repeat steps 1 to 6 until all characters in s have been selected.
  • At any step, if there is more than one smallest or largest character, you can choose any of them and append it to the result string.

Please return the result string after reordering the characters in s.

Example

Input: s = "aaaabbbbcccc" Output: "abccbaabccba" Explanation: After the first round of steps 1, 2, and 3, the result string is result = "abc" After the first round of steps 4, 5, and 6, the result string is result = "abccba" First round ends, now s = "aabbcc", and we return to step 1 again After the second round of steps 1, 2, and 3, the result string is result = "abccbaabc" After the second round of steps 4, 5, and 6, the result string is result = "abccbaabccba"
Input: s = "rat" Output: "art" Explanation: The word "rat" becomes "art" after reordering with the algorithm above.
Input: s = "leetcode" Output: "cdelotee"

Solution

/**
 * @param {string} s
 * @return {string}
 */
var sortString = function(s) {
    let hashTable = Object.create(null);
    let base = "a".charCodeAt();
    for(let i=0;i<26;++i) hashTable[String.fromCharCode(base+i)] = 0;
    Array.prototype.forEach.call(s, v => hashTable[v]++);
    let target = "";
    while(target.length < s.length){
        for(let i=0;i<26;++i) {
            let key = String.fromCharCode(base+i);
            if(hashTable[key]){
                target += key;
                hashTable[key]--;
            }
        }
        for(let i=25;i>=0;--i) {
            let key = String.fromCharCode(base+i);
            if(hashTable[key]){
                target += key;
                hashTable[key]--;
            }
        }
    }
    return target;
};

Idea

The question is quite long, but it's just regular string manipulation. Moreover, because the question specifies that it's pure lowercase letters, the total quantity is fixed. Hence, there's no need to use sorting to count occurrences. The subsequent operations are simply sequential traversal and reverse traversal. First, define a pure object as a hash table to record the number of each character in the string. Then, define the base value of lowercase characters as the ASCII value of 'a' and construct a loop for the 26 lowercase letters, with the initial value in the hash table corresponding to the key being defined as 0. Loop through the string to count occurrences, define the target string, and if the target string is equal in length to the given string, exit the loop. Then, define a loop for the 26 letters in the positive direction, and if the value of this letter is greater than 0 in the hash table, append it to the target string and decrement the value. Then, define a reverse loop for the 26 letters, and append the character according to the same rule. After finishing the loop, return the target string.

Daily Problem

https://github.com/WindrunnerMax/EveryDay

Reference

https://leetcode-cn.com/problems/increasing-decreasing-string/