Problem Description

Given a string s consisting only of lowercase English letters, you are to reorder the string using the following algorithm:

1. Pick the smallest character from s and append it to the result.
2. Pick the smallest character from s that is greater than the last appended character and append it to the result.
3. Repeat step 2 until you cannot pick more characters in this pass.
4. Pick the largest character from s and append it to the result.
5. Pick the largest character from s that is smaller than the last appended character and append it to the result.
6. Repeat step 5 until you cannot pick more characters in this pass.
7. Repeat steps 1-6 until all the characters from s have been used.

You must not reuse any character from s. The final result will be a permutation of the original string. There is always exactly one valid answer for each input.

Thought Process

At first glance, the problem seems to require repeatedly finding the next smallest or largest unused character in the string, alternating between ascending and descending order. A brute-force approach would be to scan the string for the next smallest or largest character each time, but this would be inefficient.

To optimize, we can observe that all characters are lowercase English letters, so there are only 26 possible characters. Instead of searching the string repeatedly, we can count the frequency of each character and use this information to efficiently pick the next available character in either ascending or descending order.

This approach avoids unnecessary scans and leverages the limited alphabet size, leading to a much faster solution. The problem becomes one of managing character counts and iterating in both directions over the alphabet.

Solution Approach

Here is a step-by-step breakdown of the optimized algorithm:

1. Count Character Frequencies:
   • Create an array (or map) of size 26 to store the count of each character in s.
2. Build the Result:
   • Initialize an empty result string.
   • While there are still characters left (i.e., the sum of all counts is greater than zero):
   • Ascending Pass:
     • Iterate from 'a' to 'z' (indexes 0 to 25).
     • If the count for a character is greater than 0, append it to the result and decrement the count.
   • Descending Pass:
     • Iterate from 'z' to 'a' (indexes 25 to 0).
     • If the count for a character is greater than 0, append it to the result and decrement the count.
3. Return the Result:
   • Once all characters have been used, return the built result string.

This approach is efficient because each character is processed exactly as many times as it appears in the input, and all operations on the count array are O(1).

Example Walkthrough

Let's walk through an example with s = "aaaabbbbcccc":

1. Initial counts: a:4, b:4, c:4
2. First Ascending Pass:
   • Pick 'a' (result: "a", counts: a:3, b:4, c:4)
   • Pick 'b' (result: "ab", counts: a:3, b:3, c:4)
   • Pick 'c' (result: "abc", counts: a:3, b:3, c:3)
3. First Descending Pass:
   • Pick 'c' (result: "abcc", counts: a:3, b:3, c:2)
   • Pick 'b' (result: "abccb", counts: a:3, b:2, c:2)
   • Pick 'a' (result: "abccba", counts: a:2, b:2, c:2)
4. Second Ascending Pass:
   • Pick 'a' (result: "abccbaa", counts: a:1, b:2, c:2)
   • Pick 'b' (result: "abccbaab", counts: a:1, b:1, c:2)
   • Pick 'c' (result: "abccbaabc", counts: a:1, b:1, c:1)
5. Second Descending Pass:
   • Pick 'c' (result: "abccbaabcc", counts: a:1, b:1, c:0)
   • Pick 'b' (result: "abccbaabccb", counts: a:1, b:0, c:0)
   • Pick 'a' (result: "abccbaabccba", counts: a:0, b:0, c:0)
6. All characters used. Final result: abccbaabccba

Time and Space Complexity

Brute-Force Approach:

• Each time we look for the next smallest or largest unused character, we scan the entire string. Each character can be picked up to N times, so the total time complexity is O(N²).
• Space complexity is O(N) for the result string.

• We count frequencies in O(N) time.
• Each ascending and descending pass goes over 26 letters, and we do as many passes as needed to use all N letters. In total, each letter is appended once per its occurrence, so time complexity is O(N + K), where K=26 (a constant), so O(N).
• Space complexity is O(N) for the result and O(1) for the frequency array (since the alphabet size is fixed).

Summary

This problem can be solved efficiently by leveraging the limited size of the lowercase English alphabet. By counting character frequencies and iterating in both ascending and descending order, we avoid unnecessary scans and achieve an O(N) solution. The key insight is to use a counting array for constant-time access, making the implementation both simple and optimal.

Code Implementation

class Solution:
    def sortString(self, s: str) -> str:
        counts = [0] * 26
        for c in s:
            counts[ord(c) - ord('a')] += 1
        result = []
        n = len(s)
        while len(result) < n:
            # Ascending pass
            for i in range(26):
                if counts[i]:
                    result.append(chr(i + ord('a')))
                    counts[i] -= 1
            # Descending pass
            for i in range(25, -1, -1):
                if counts[i]:
                    result.append(chr(i + ord('a')))
                    counts[i] -= 1
        return ''.join(result)
      

class Solution {
public:
    string sortString(string s) {
        vector<int> counts(26, 0);
        for (char c : s) {
            counts[c - 'a']++;
        }
        string result;
        int n = s.size();
        while (result.size() < n) {
            // Ascending pass
            for (int i = 0; i < 26; ++i) {
                if (counts[i]) {
                    result += (char)('a' + i);
                    counts[i]--;
                }
            }
            // Descending pass
            for (int i = 25; i >= 0; --i) {
                if (counts[i]) {
                    result += (char)('a' + i);
                    counts[i]--;
                }
            }
        }
        return result;
    }
};
      

class Solution {
    public String sortString(String s) {
        int[] counts = new int[26];
        for (char c : s.toCharArray()) {
            counts[c - 'a']++;
        }
        StringBuilder result = new StringBuilder();
        int n = s.length();
        while (result.length() < n) {
            // Ascending pass
            for (int i = 0; i < 26; i++) {
                if (counts[i] > 0) {
                    result.append((char) (i + 'a'));
                    counts[i]--;
                }
            }
            // Descending pass
            for (int i = 25; i >= 0; i--) {
                if (counts[i] > 0) {
                    result.append((char) (i + 'a'));
                    counts[i]--;
                }
            }
        }
        return result.toString();
    }
}
      

var sortString = function(s) {
    let counts = new Array(26).fill(0);
    for (let c of s) {
        counts[c.charCodeAt(0) - 'a'.charCodeAt(0)]++;
    }
    let result = [];
    let n = s.length;
    while (result.length < n) {
        // Ascending pass
        for (let i = 0; i < 26; i++) {
            if (counts[i] > 0) {
                result.push(String.fromCharCode(i + 'a'.charCodeAt(0)));
                counts[i]--;
            }
        }
        // Descending pass
        for (let i = 25; i >= 0; i--) {
            if (counts[i] > 0) {
                result.push(String.fromCharCode(i + 'a'.charCodeAt(0)));
                counts[i]--;
            }
        }
    }
    return result.join('');
};