Increasing Decreasing String

Difficulty: Easy | Acceptance: 77.30% | Paid: No Topics: Hash Table, String, Counting

You are given a string s. 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 which is greater than the last appended character to the result and append it.
3. Repeat step 2 until you cannot pick a character.
4. Pick the largest character from s and append it to the result.
5. Pick the largest character from s which is smaller than the last appended character to the result and append it.
6. Repeat step 5 until you cannot pick a character.
7. Repeat the process from step 1 until you pick all characters from s.

Return the resulting string.

• Examples
• Constraints
• Counting Sort (Frequency Array)
• Sorting and Simulation

Examples

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".
The first iteration is finished. Now, s = "aabbcc" and we repeat steps 1-6.
Result = "abccbaabccba"

Example 2

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

Constraints

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

Counting Sort (Frequency Array)

Intuition Since the input string consists only of lowercase English letters, we can use a fixed-size array of length 26 to count the frequency of each character. This allows us to efficiently pick the smallest and largest available characters in linear time.

Steps

• Create an integer array count of size 26 initialized to 0.
• Iterate through the string s and increment the count for each character.
• Initialize an empty result string (or list).
• While the length of the result is less than the length of s:
  • Iterate from index 0 to 25 (a to z). If count[i] > 0, append the character to the result and decrement count[i].
  • Iterate from index 25 down to 0 (z to a). If count[i] > 0, append the character to the result and decrement count[i].
• Return the result.

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

Complexity

• Time: O(N), where N is the length of the string. We iterate through the string to count and then iterate through the fixed 26-character alphabet to build the result.
• Space: O(1) auxiliary space, as we use a fixed-size array of 26 integers regardless of the input size.
• Notes: This is the most optimal approach for this problem given the constraints on character set.

Sorting and Simulation

Intuition We can sort the string first to easily access the smallest and largest characters. Then, we simulate the picking process by scanning the sorted list and removing characters as we pick them.

Steps

• Convert the string s into a list of characters and sort it.
• Initialize an empty result list.
• While the character list is not empty:
  • Increasing Phase: Iterate through the list. If the current character is greater than the last picked character (or if it’s the first pick), append it to the result and remove it from the list.
  • Decreasing Phase: Iterate through the list. If the current character is smaller than the last picked character (or if it’s the first pick), append it to the result and remove it from the list.
• Return the joined result string.

class Solution:
    def sortString(self, s: str) -> str:
        chars = sorted(s)
        res = []
        
        while chars:
            # Increasing phase
            i = 0
            last = ''
            while i < len(chars):
                if chars[i] > last:
                    last = chars[i]
                    res.append(chars.pop(i))
                else:
                    i += 1
            
            # Decreasing phase
            i = 0
            last = '{' # Character after 'z'
            while i < len(chars):
                if chars[i] < last:
                    last = chars[i]
                    res.append(chars.pop(i))
                else:
                    i += 1
                    
        return ''.join(res)

Complexity

• Time: O(N²), where N is the length of the string. Sorting takes O(N log N), but removing elements from a list/array takes O(N) in the worst case, and we do this N times.
• Space: O(N) to store the list of characters.
• Notes: This approach is intuitive but less efficient than Counting Sort due to the cost of element removal.