Increasing Decreasing String

Increasing Decreasing String

What is this problem about?

The Increasing Decreasing String coding problem asks you to reorder characters from a given string into a new string using a specific multi-step algorithm:

1. Pick the smallest character, then the next smallest unique character, and so on until you can't pick any more (increasing).
2. Pick the largest character, then the next largest unique character, and so on until you can't pick any more (decreasing).
3. Repeat until all characters are used.

Why is this asked in interviews?

Amazon and Akuna Capital use this "Easy" question to test your ability to handle frequency maps and structured iteration. It evaluations whether you can manage counts effectively and implement a "zig-zag" iteration over a range of values. It’s a test of code organization and attention to procedural rules.

Algorithmic pattern used

The problem uses Frequency Counting and Bidirectional Iteration.

1. Count the frequency of each character 'a'-'z' and store it in an array of size 26.
2. While there are characters remaining (track using a totalCount or the array itself):
   • Step 1 (Smallest to Largest): Loop from index 0 to 25. If count > 0, append character to result and decrement count.
   • Step 2 (Largest to Smallest): Loop from index 25 to 0. If count > 0, append character to result and decrement count.

Example explanation

String: "aaaabbbccc"

1. Counts: {a: 4, b: 3, c: 3}.
2. Pass 1 (Up): Pick 'a', 'b', 'c'. Result: "abc". Counts: {a: 3, b: 2, c: 2}.
3. Pass 1 (Down): Pick 'c', 'b', 'a'. Result: "abccba". Counts: {a: 2, b: 1, c: 1}.
4. Pass 2 (Up): Pick 'a', 'b', 'c'. Result: "abccbaabc". Counts: {a: 1, b: 0, c: 0}.
5. Pass 2 (Down): Pick 'a'. Result: "abccbaabca". Result: "abccbaabca".

Common mistakes candidates make

• Sorting repeatedly: Trying to sort the string multiple times instead of using a single frequency map.
• Unique picking: Forgetting that each pass only picks one instance of each character available.
• Loop exit: Not correctly checking when all characters have been consumed.

Interview preparation tip

Frequency arrays are much more efficient than Hash Maps for lowercase English letters. Always use an int[26] for these problems to achieve $O(1)$ space (relative to the alphabet) and $O(N)$ time.