LeetCode 1370 - Increasing Decreasing String
The problem requires us to reorder a string s by repeatedly picking characters in a specific increasing and decreasing p
Difficulty: 🟢 Easy
Topics: Hash Table, String, Counting
Solution
Problem Understanding
The problem requires us to reorder a string s by repeatedly picking characters in a specific increasing and decreasing pattern. In other words, we need to simulate a process where, at each iteration, we first pick the smallest character and keep picking increasingly larger characters until we cannot pick anymore. Then, we switch directions: we pick the largest character and continue picking smaller characters until we cannot pick anymore. This process repeats until all characters are consumed.
The input is a string s of length between 1 and 500, consisting solely of lowercase English letters. The expected output is a string that represents s reordered according to the described algorithm. The constraints guarantee that the string is non-empty and that the alphabet size is limited to 26 letters, which suggests a counting or frequency-based approach may be efficient.
Edge cases to consider include strings where all characters are the same, strings already in ascending or descending order, and very short strings of length 1. The problem guarantees only lowercase letters, so we do not need to handle upper-case or special characters.
Approaches
The brute-force approach would simulate the process literally. At each step, you would scan the string to find the smallest or largest character satisfying the rules, remove it, and append it to the result. This is correct but inefficient because each scan over the string can take O(n) time, and repeated scans would result in O(n^2) time complexity, which is acceptable for n up to 500 but not optimal.
The optimal approach leverages the fact that there are only 26 possible characters. We can maintain a frequency count for each character and iterate through the alphabet in ascending and descending order, appending characters as allowed by the frequency count. This reduces repeated scanning of the string and gives a more structured, predictable iteration over character sets.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(n^2) | O(n) | Scan the string repeatedly for smallest/largest characters |
| Optimal | O(n) | O(1) | Use a fixed-size frequency array (26 letters) to track counts and iterate over characters |
Algorithm Walkthrough
- Initialize a frequency array of size 26, where each index corresponds to a lowercase letter. Count the occurrences of each character in the input string
s. - Initialize an empty list or string to store the result.
- While the length of the result is less than the length of
s, perform the following two passes: - Ascending Pass: Iterate over the frequency array from 'a' to 'z'. For each character with a non-zero frequency, append it to the result and decrement its frequency.
- Descending Pass: Iterate over the frequency array from 'z' to 'a'. For each character with a non-zero frequency, append it to the result and decrement its frequency.
- Repeat steps 3-5 until all characters are appended.
- Return the joined result as the reordered string.
Why it works: The frequency array ensures that characters are appended exactly the number of times they appear. Iterating in ascending and descending order guarantees that the algorithm follows the increasing-decreasing pattern. Since the frequency count is fixed at 26 elements, every iteration over the array is bounded and predictable.
Python Solution
class Solution:
def sortString(self, s: str) -> str:
freq = [0] * 26 # frequency array for 'a' to 'z'
for char in s:
freq[ord(char) - ord('a')] += 1
result = []
n = len(s)
while len(result) < n:
# ascending pass
for i in range(26):
if freq[i] > 0:
result.append(chr(i + ord('a')))
freq[i] -= 1
# descending pass
for i in range(25, -1, -1):
if freq[i] > 0:
result.append(chr(i + ord('a')))
freq[i] -= 1
return ''.join(result)
The implementation begins by creating a frequency array to efficiently track character counts. The while loop ensures the process continues until all characters are added. The ascending and descending passes over the frequency array simulate the problem's described algorithm. The ord and chr functions handle mapping between characters and array indices.
Go Solution
func sortString(s string) string {
freq := [26]int{}
for _, char := range s {
freq[char - 'a']++
}
result := make([]byte, 0, len(s))
for len(result) < len(s) {
// ascending pass
for i := 0; i < 26; i++ {
if freq[i] > 0 {
result = append(result, byte('a'+i))
freq[i]--
}
}
// descending pass
for i := 25; i >= 0; i-- {
if freq[i] > 0 {
result = append(result, byte('a'+i))
freq[i]--
}
}
}
return string(result)
}
In Go, we use a fixed-size array [26]int to store frequencies and a byte slice for the result. Conversion between indices and characters uses arithmetic with 'a'. Slice appending is efficient because we preallocate capacity.
Worked Examples
Example 1: "aaaabbbbcccc"
| Step | Ascending Pass | Descending Pass | Result |
|---|---|---|---|
| 1 | a,b,c | c,b,a | abccba |
| 2 | a,b,c | c,b,a | abccbaabccba |
Example 2: "rat"
| Step | Ascending Pass | Descending Pass | Result |
|---|---|---|---|
| 1 | a,r,t | t,r,a | art |
The frequency array ensures that each character is picked correctly, following ascending and descending patterns until all are exhausted.
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n) | Each character is appended exactly once; we iterate over a fixed 26-letter array repeatedly |
| Space | O(1) | Frequency array is fixed size 26; result uses O(n) which is output space |
Because the alphabet size is constant (26), iterating over the frequency array does not scale with n, making the algorithm effectively linear.
Test Cases
# provided examples
assert Solution().sortString("aaaabbbbcccc") == "abccbaabccba" # mixed repeating
assert Solution().sortString("rat") == "art" # simple case
# additional cases
assert Solution().sortString("a") == "a" # single character
assert Solution().sortString("zyx") == "xyz" # descending input
assert Solution().sortString("abcabc") == "abcabc" # already mixed order
assert Solution().sortString("bbbb") == "bbbb" # all same character
assert Solution().sortString("aabbccddeeffgghh") == "abcdefghhgfedcba" # longer repeating
| Test | Why |
|---|---|
"aaaabbbbcccc" |
tests repeated characters with full ascending-descending cycles |
"rat" |
minimal case with distinct characters |
"a" |
single-character edge case |
"zyx" |
input already descending |
"abcabc" |
alternating sequence with duplicates |
"bbbb" |
all characters identical |
"aabbccddeeffgghh" |
longer string with many duplicates |
Edge Cases
One important edge case is a string with all identical characters, such as "bbbb". A naive algorithm may try to pick the next character greater than the last appended, but since there is none, it must properly handle repeating the same character until exhausted.
Another edge case is a single-character string. The algorithm must return the same character without entering unnecessary loops or causing out-of-bounds errors.
A third edge case involves strings in reverse order, such as "zyx". The algorithm must correctly handle descending sequences at the beginning and not assume ascending order initially, ensuring the result is still sorted according to the defined increasing-decreasing pattern.