Increasing Decreasing String: Zigzag Character Picking

LeetCode Increasing Decreasing String (problem 1370) asks you to reorder a string using a specific zigzag procedure. Given a string s, you build a new result by repeatedly picking the smallest character not yet chosen, then the next smallest, and so on until no more increasing picks are possible. Then you reverse direction and pick the largest remaining character, then the next largest, and so on. You keep alternating between increasing and decreasing passes until every character has been placed.

Why this problem matters

This problem is a clean exercise in two fundamental techniques: character frequency counting and ordered iteration over a fixed alphabet. Both show up constantly in string problems, and this problem combines them in a way that feels natural once you see it.

The zigzag pattern also teaches you to think about iterating over a structure in both directions. Many problems ask you to sweep left-to-right and then right-to-left, whether it is over an array, a string, or an alphabet. Recognizing that forward and backward passes can be combined into a single loop is a useful mental model.

Finally, the fixed 26-letter alphabet makes this problem a great introduction to the idea of using constant-space frequency arrays instead of hash maps. When the key set is small and known, an array is simpler and faster.

The key insight

You do not need to sort the string or build any complex data structure. Instead, count the frequency of each character in a size-26 array. Then alternate between two sweeps:

1. Increasing pass: walk from index 0 (representing 'a') to index 25 (representing 'z'). For every character with a remaining count greater than 0, append it to the result and decrement the count.
2. Decreasing pass: walk from index 25 back to index 0. Same rule: if the count is positive, append and decrement.

Repeat until all characters are consumed. Each pass picks characters in sorted order (ascending or descending), and decrementing the count ensures each occurrence is used exactly once.

The solution

def sort_string(s: str) -> str:
    freq = [0] * 26
    for ch in s:
        freq[ord(ch) - ord('a')] += 1

    result = []
    while len(result) < len(s):
        # Increasing pass: a to z
        for i in range(26):
            if freq[i] > 0:
                result.append(chr(i + ord('a')))
                freq[i] -= 1
        # Decreasing pass: z to a
        for i in range(25, -1, -1):
            if freq[i] > 0:
                result.append(chr(i + ord('a')))
                freq[i] -= 1

    return ''.join(result)

The code starts by building the frequency array. For each character in s, it increments the corresponding slot using ord(ch) - ord('a') to map 'a' through 'z' to indices 0 through 25.

The main loop runs until the result has the same length as the input. Inside, it performs two passes. The first sweeps from 0 to 25, appending any character that still has remaining occurrences. The second sweeps from 25 down to 0, doing the same thing. After both passes, one full "zigzag" round is complete.

The while loop terminates because each pass consumes at least one character (as long as any remain), so the result grows by at least one character per pass.

Visual walkthrough

Notice how each increasing pass picks characters in alphabetical order, and each decreasing pass picks them in reverse. The frequency array shrinks uniformly because the input has equal counts for each letter. With unequal counts, some letters would be skipped in later passes once their count reaches zero.

Complexity analysis

Time is O(n) because you do O(n) work to build the frequency array, and the total work across all zigzag passes is also O(n). Each pass iterates over at most 26 slots, and across all passes, exactly n characters are appended. So the total number of inner-loop iterations is at most 26 * (number of passes), and each pass adds at least one character, giving at most n passes. But in practice, each pass adds many characters, and the total work stays proportional to n.

Space is O(1) because the frequency array has a fixed size of 26, regardless of the input length. The result string uses O(n) space, but that is required for the output itself.

The building blocks

1. Character frequency counting

Counting character frequencies with a fixed-size array is a pattern you will see in dozens of problems. Valid Anagram, Group Anagrams, Ransom Note, and Sort Characters By Frequency all start with the same step. The key idea is that when your keys are drawn from a small known set (like lowercase English letters), an array is better than a hash map. It is faster, uses less memory, and gives you ordered access by default.

freq = [0] * 26
for ch in s:
    freq[ord(ch) - ord('a')] += 1

This three-line pattern should be automatic. You will write it often enough that it should feel like typing your own name.

2. Ordered alphabet traversal

Once you have the frequency array, iterating over it in order gives you characters sorted alphabetically. Iterating in reverse gives you characters in reverse alphabetical order. This is the second building block: using array index order as a substitute for sorting.

# Forward: a to z
for i in range(26):
    if freq[i] > 0:
        # process chr(i + ord('a'))

# Backward: z to a
for i in range(25, -1, -1):
    if freq[i] > 0:
        # process chr(i + ord('a'))

This bidirectional sweep pattern shows up whenever you need to alternate between smallest-first and largest-first selection.

Edge cases

• Single character "a": one increasing pass picks 'a', result is "a". No decreasing pass needed.
• All same characters "aaaa": each pass picks one 'a', alternating between increasing and decreasing. Result is "aaaa".
• Already sorted "abc": one increasing pass picks 'a', 'b', 'c'. All characters consumed. Result is "abc".
• Reverse sorted "cba": one increasing pass picks 'a', 'b', 'c' (frequency array orders them). Result is "abc".
• Two characters with unequal counts "aaab": increasing picks 'a', 'b'. Decreasing picks 'a'. Increasing picks 'a'. Result is "abaa".
• Full alphabet with one of each letter: one increasing pass consumes everything in order.

From understanding to recall

This problem is easy to understand but surprisingly easy to get wrong from memory. The details that trip people up are the direction of each pass (forward then backward, not the other way around), the loop bounds (range(25, -1, -1) to include index 0), and the termination condition (check total length, not pass count).

The pattern itself, counting frequencies and sweeping in alternating directions, is a building block that transfers to harder problems. Sort Characters By Frequency uses the same frequency array but sorts by count instead of alphabetical order. Group Anagrams uses the frequency array as a hash key. Valid Anagram compares two frequency arrays. Each of these starts with the same three-line counting step.

Practice writing the zigzag loop from scratch a few times. Once you can produce the frequency array, the forward sweep, and the backward sweep without hesitation, you own both this problem and the reusable pieces that compose it.

Related posts

• Sort Characters by Frequency - Character frequency sorting
• Group Anagrams - Character frequency as key
• Valid Anagram - Character counting fundamentals

This problem distills string manipulation down to its core: count, sweep, repeat. CodeBricks breaks it into those building blocks and drills them with spaced repetition until the pattern is automatic. When a character-frequency question shows up in your interview, you do not think about it. You just write it.