Increasing Decreasing String - Video Solutions
LeetCode 1370 | Increasing Decreasing String | Algorithm Explained (Java + Whiteboard)
Increasing Decreasing String - Video Solution
Watch 10 video solutions for Increasing Decreasing String, a easy level problem involving Hash Table, String, Counting. This walkthrough by Xavier Elon has 3,600 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
You are given a string s. Reorder the string using the following algorithm:
- Remove the smallest character from
sand append it to the result. - Remove the smallest character from
sthat is greater than the last appended character, and append it to the result. - Repeat step 2 until no more characters can be removed.
- Remove the largest character from
sand append it to the result. - Remove the largest character from
sthat is smaller than the last appended character, and append it to the result. - Repeat step 5 until no more characters can be removed.
- Repeat steps 1 through 6 until all characters from
shave been removed.
If the smallest or largest character appears more than once, you may choose any occurrence to append to the result.
Return the resulting string after reordering s using this algorithm.
Example 1:
Input: s = "aaaabbbbcccc" Output: "abccbaabccba" Explanation: After steps 1, 2 and 3 of the first iteration, result = "abc" After steps 4, 5 and 6 of the first iteration, result = "abccba" First iteration is done. Now s = "aabbcc" and we go back to step 1 After steps 1, 2 and 3 of the second iteration, result = "abccbaabc" After steps 4, 5 and 6 of the second iteration, result = "abccbaabccba"
Example 2:
Input: s = "rat" Output: "art" Explanation: The word "rat" becomes "art" after re-ordering it with the mentioned algorithm.
Constraints:
1 <= s.length <= 500sconsists of only lowercase English letters.
Approach Overview
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.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two Pointers + Sorting | O(n log n) | O(n) | Simple simulation when sorting is acceptable and implementation clarity matters |
| Counting Sort / Frequency Array | O(n) | O(1) | Best choice when characters are limited (26 lowercase letters) and optimal performance is required |