Increasing Decreasing String — Problem & Solution
Increasing Decreasing String solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Increasing Decreasing String is an easy coding problem on strings, hash table and counting, asked in Amazon and Adobe interviews.
- Difficulty: Easy
- Topics: Strings, Hash Table, Counting
- Asked at: Amazon, Adobe
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Rebuild the lowercase string s by repeatedly moving its characters to a result, using this procedure:
- Take the smallest character left in
sand append it to the result. - Take the smallest character left that is strictly greater than the last one appended, and append it. Repeat until no such character exists.
- Take the largest character left in
sand append it. - Take the largest character left that is strictly smaller than the last one appended, and append it. Repeat until no such character exists.
- Go back to step 1 until every character of
shas been used.
Whenever a character occurs several times you may take any copy — the result is the same. Return the result string.
Example 1
Input: s = "kairokairo"
Output: aikorrokia
Explanation: Rising pass `aikor`, falling pass `rokia`.
Example 2
Input: s = "codekairo"
Output: acdeikoro
Explanation: Rising pass `acdeikor` leaves one `o` for the falling pass.
Example 3
Input: s = "zzz"
Output: zzz
Constraints
1 <= s.length <= 500s consists of only lowercase English letters
Hints for Increasing Decreasing String
Hint 1
Only how many copies of each letter are left matters, not where they were.
Hint 2
Keep a count for each of the 26 letters.
Hint 3
One rising pass is a walk a→z taking one copy of every letter still available; a falling pass is the same walk z→a. Alternate until the counts are empty.
How to solve Increasing Decreasing String
Each rising pass takes exactly one copy of every letter that is still available, in alphabetical order, and each falling pass does the same in reverse — so a 26-entry count table replaces any searching.
Approach
- Count the occurrences of each letter.
- While the result is shorter than
s: walk the letters fromatoz, appending each letter whose count is positive and decrementing it. - Then walk from
ztoathe same way. - Return the result.
Why it works
In a rising pass the first pick is the smallest available letter, and each following pick is the smallest available letter strictly greater than the previous one — exactly the next letter with a positive count in alphabetical order. The pass ends when no larger letter is left, i.e. when the walk reaches z. The falling pass is symmetric. Each full round removes at least one character, so the loop ends.
Complexity
- Time —
O(26 · rounds + n) = O(n) - Space —
O(1) besides the output
Pitfalls
- "Strictly greater" means one copy per letter per pass — duplicates wait for later passes.
- The falling pass starts from the largest remaining letter, not from the last letter appended.
- Stop as soon as all characters are used; an empty pass is harmless but the length check must cover both halves.
Reference solution
Python
def sortString(s: str) -> str:
cnt = [0] * 26
for c in s:
cnt[ord(c) - 97] += 1
order = list(range(26)) + list(range(25, -1, -1))
res = []
while len(res) < len(s):
for i in order:
if cnt[i] > 0:
res.append(chr(97 + i))
cnt[i] -= 1
return ''.join(res)Java
public static String sortString(String s) {
int[] cnt = new int[26];
for (int i = 0; i < s.length(); i++) cnt[s.charAt(i) - 'a']++;
StringBuilder res = new StringBuilder();
while (res.length() < s.length()) {
for (int a = 0; a < 26; a++) if (cnt[a] > 0) { res.append((char) ('a' + a)); cnt[a]--; }
for (int b = 25; b >= 0; b--) if (cnt[b] > 0) { res.append((char) ('a' + b)); cnt[b]--; }
}
return res.toString();
}C++
string sortString(string s) {
int cnt[26] = {0};
for (char c : s) cnt[c - 'a']++;
string res;
while (res.size() < s.size()) {
for (int a = 0; a < 26; a++) if (cnt[a] > 0) { res += (char)('a' + a); cnt[a]--; }
for (int b = 25; b >= 0; b--) if (cnt[b] > 0) { res += (char)('a' + b); cnt[b]--; }
}
return res;
}JavaScript
var sortString = function(s) {
var cnt = [];
for (var z = 0; z < 26; z++) cnt.push(0);
for (var i = 0; i < s.length; i++) cnt[s.charCodeAt(i) - 97]++;
var res = [];
while (res.length < s.length) {
for (var a = 0; a < 26; a++) if (cnt[a] > 0) { res.push(String.fromCharCode(97 + a)); cnt[a]--; }
for (var b = 25; b >= 0; b--) if (cnt[b] > 0) { res.push(String.fromCharCode(97 + b)); cnt[b]--; }
}
return res.join("");
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Hashing: Hash Maps and Hash Sets