Increasing Decreasing String - Video Solutions

Problem Overview: Given a string s, repeatedly build a result string by selecting characters in increasing alphabetical order, then decreasing order, and repeat until all characters are used. Each step picks the smallest available character greater than the last chosen one, then reverses direction.

Approach 1: Two Pointers and Sorting (O(n log n) time, O(n) space)

Sort the characters of the string first. Once sorted, simulate the increasing and decreasing passes using two pointers or directional iteration. During the increasing phase, iterate left to right and pick the next unused character that is strictly larger than the previous pick. During the decreasing phase, iterate right to left and apply the same rule. Mark characters as used or remove them from the structure. Sorting dominates the runtime with O(n log n) complexity, while the extra storage for tracking usage gives O(n) space.

This approach is straightforward because sorting already groups characters in alphabetical order. The logic mirrors the problem description closely, making it useful for quick implementation or when explaining the idea during interviews.

Approach 2: Counting Sort / Frequency Array (O(n) time, O(1) space)

Instead of sorting the entire string, count the frequency of each lowercase letter using a fixed array of size 26. This leverages the limited alphabet constraint. First iterate from 'a' to 'z', appending a character if its frequency is still positive and decrementing the count. Then iterate from 'z' back to 'a' and repeat the process. Continue alternating these passes until the result length matches the input length.

The key insight is that the alphabet size is constant. Each pass checks at most 26 characters, so the algorithm runs in linear time relative to the input size. The frequency array requires constant extra memory, resulting in O(1) auxiliary space.

This technique is essentially a specialized counting strategy combined with repeated ordered traversal. It avoids the overhead of full sorting and works particularly well for problems involving limited character sets. The implementation relies heavily on simple array indexing and character arithmetic.

Recommended for interviews: The counting-based approach is the solution most interviewers expect. It shows you recognize the constrained alphabet and apply a frequency array instead of sorting. Mentioning the sorting simulation first demonstrates problem understanding, while implementing the frequency counting strategy highlights algorithmic optimization for string problems.