Increasing Decreasing String - Solution & Explanation
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.
Approach 1: Counting Sort Approach
This approach uses frequency counting of characters to build the result string. We maintain a count of each character using an array of size 26 (for each letter in the English alphabet). We repeatedly iterate over this count array to construct the result as per the given algorithm.
In this C implementation, we use an array of size 26 to count the occurrences of each character in the string. We perform two loops: one (to append characters from smallest to largest) and another (from largest to smallest). We repeat these steps until the resultant string is constructed.
Complexity
Time Complexity: O(n) - We make a constant 52 iterations for each character.
Space Complexity: O(1) - Constant space is used for the count array.
Approach 2: Two Pointers and Sorting Approach
In this approach, we first sort the string. We then utilize two pointers: one starting from the beginning and the other starting from the end. These two pointers help us alternate between choosing the smallest and largest characters.
This approach involves sorting the string first. We manage two pointers and alter between collecting elements from start and end. This way, we maintain an order that meets the requirements while traversing the characters.
Complexity
Time Complexity: O(n log n) - due to sorting the string initially.
Space Complexity: O(n) - Extra space for result storage.
Approach 3: Counting + Simulation
First, we use a hash table or an array cnt of length 26 to count the number of occurrences of each character in the string s.
Then, we enumerate the letters [a,...,z]. For the current enumerated letter c, if cnt[c] > 0, we append the letter c to the end of the answer string and decrease cnt[c] by one. We repeat this step until cnt[c] = 0. Then we enumerate the letters [z,...,a] in reverse order and perform similar operations. If the length of the answer string equals the length of s, then we have completed all the concatenation operations.
The time complexity is O(n times |\Sigma|), and the space complexity is O(|\Sigma|). Where n is the length of the string s, and \Sigma is the character set. In this problem, the character set is all lowercase letters, so |\Sigma| = 26.
Code
Python
Java
C++
Go
TypeScript
JavaScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Counting Sort Approach | Time Complexity: O(n) - We make a constant 52 iterations for each character. |
| Two Pointers and Sorting Approach | Time Complexity: O(n log n) - due to sorting the string initially. |
| Counting + Simulation | — |
Detailed 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 |
Video Solution
LeetCode 1370 | Increasing Decreasing String | Algorithm Explained (Java + Whiteboard) • Xavier Elon • 3,600 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Increasing Decreasing String easy or hard?
How to solve Increasing Decreasing String in O(n)?
Increasing Decreasing String Python or Java solution?
What is the best approach for Increasing Decreasing String?
What data structure is used in Increasing Decreasing String?
What is the time complexity of Increasing Decreasing String?
Is Increasing Decreasing String asked at Google, Amazon, or Meta?
Ready to solve this problem?
Practice Increasing Decreasing String with our built-in code editor and test cases.
Practice on FleetCode