Increasing Decreasing String

Easy
1179.

Increasing Decreasing String

Increasing Decreasing String is an easy coding problem on strings, hash table and counting, asked in Amazon and Adobe interviews.

Rebuild the lowercase string s by repeatedly moving its characters to a result, using this procedure:

  1. Take the smallest character left in s and append it to the result.
  2. Take the smallest character left that is strictly greater than the last one appended, and append it. Repeat until no such character exists.
  3. Take the largest character left in s and append it.
  4. Take the largest character left that is strictly smaller than the last one appended, and append it. Repeat until no such character exists.
  5. Go back to step 1 until every character of s has 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 <= 500
  • s consists of only lowercase English letters
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @return {string}
 */
var sortString = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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:

  1. Take the smallest character left in s and append it to the result.
  2. Take the smallest character left that is strictly greater than the last one appended, and append it. Repeat until no such character exists.
  3. Take the largest character left in s and append it.
  4. Take the largest character left that is strictly smaller than the last one appended, and append it. Repeat until no such character exists.
  5. Go back to step 1 until every character of s has 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 <= 500
  • s consists of only lowercase English letters

Hints for Increasing Decreasing String

  1. Hint 1

    Only how many copies of each letter are left matters, not where they were.

  2. Hint 2

    Keep a count for each of the 26 letters.

  3. 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

  1. Count the occurrences of each letter.
  2. While the result is shorter than s: walk the letters from a to z, appending each letter whose count is positive and decrementing it.
  3. Then walk from z to a the same way.
  4. 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