1. Increasing Decreasing String (LeetCode)
Model answer
The task
Reorder the characters by repeatedly taking the smallest remaining character, then the largest remaining character, alternating those two passes until all characters are used.
Key idea
Count each lowercase letter, then scan the alphabet forward and backward, taking each available letter at most once per pass. A fixed-size frequency table avoids repeatedly sorting the remaining characters.
Approach
- Count the occurrences of each letter.
- While letters remain, scan from
atoz, appending and decrementing each available count. - Scan from
ztoathe same way. - Stop early if the forward scan used the final letter.
class Solution:
def sortString(self, s: str) -> str:
counts = [0] * 26
for ch in s:
counts[ord(ch) - ord("a")] += 1
result = []
remaining = len(s)
while remaining:
# Take available letters in increasing order.
for i in range(26):
if counts[i]:
result.append(chr(ord("a") + i))
counts[i] -= 1
remaining -= 1
# The forward pass may have used the final letter.
if remaining == 0:
break
# Take available letters in decreasing order.
for i in range(25, -1, -1):
if counts[i]:
result.append(chr(ord("a") + i))
counts[i] -= 1
remaining -= 1
return "".join(result)
Complexity:
- Time: O(n), since each pass scans a fixed 26-letter alphabet.
- Space: O(1) auxiliary space for the frequency table, excluding the O(n) result.
Common follow-ups
- What if the input includes arbitrary Unicode characters? Use a dictionary of character counts and scan sorted distinct keys in each direction.
- Can the result be built without storing a frequency table? Yes, but repeatedly searching and removing characters is generally less efficient.
- What if the alphabet is much larger? A frequency map still counts efficiently, but ordering its distinct keys may add sorting cost.