1370. Increasing Decreasing String Solution

The problem

You are given a string s. Reorder the string using the following algorithm:

Remove the smallest character from s and append it to the result.
Remove the smallest character from s that 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 s and append it to the result.
Remove the largest character from s that 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 s have 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 <= 500
s consists 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.

Python

def sortString(s):
    count = [0] * 26
    for c in s:
        count[ord(c) - ord('a')] += 1
    result = []
    while len(result) < len(s):
        # Smallest to largest
        for i in range(26):
            if count[i] > 0:
                result.append(chr(i + ord('a')))
                count[i] -= 1
        # Largest to smallest
        for i in range(25, -1, -1):
            if count[i] > 0:
                result.append(chr(i + ord('a')))
                count[i] -= 1
    return ''.join(result)

s = "rat"
print(sortString(s))

Java

public class Main {
    public static String sortString(String s) {
        int[] count = new int[26];
        for (char ch : s.toCharArray())
            count[ch - 'a']++;
        StringBuilder result = new StringBuilder();
        while (result.length() < s.length()) {
            // Smallest to largest
            for (int i = 0; i < 26; i++) {
                if (count[i] > 0) {
                    result.append((char) (i + 'a'));
                    count[i]--;
                }
            }
            // Largest to smallest
            for (int i = 25; i >= 0; i--) {
                if (count[i] > 0) {
                    result.append((char) (i + 'a'));
                    count[i]--;
                }
            }
        }
        return result.toString();
    }

    public static void main(String[] args) {
        String s = "aaaabbbbcccc";
        System.out.println(sortString(s));
    }
}

C++

#include <iostream>
#include <string>
#include <vector>
using namespace std;

string sortString(string s) {
    vector<int> count(26, 0);
    for (char c : s)
        count[c - 'a']++;

    string result;
    int total = s.size();
    while (result.size() < total) {
        // Smallest to largest
        for (int i = 0; i < 26; i++) {
            if (count[i] > 0) {
                result += ('a' + i);
                count[i]--;
            }
        }
        // Largest to smallest
        for (int i = 25; i >= 0; i--) {
            if (count[i] > 0) {
                result += ('a' + i);
                count[i]--;
            }
        }
    }
    return result;
}

int main() {
    string s = "rat";
    cout << sortString(s) << endl;
    return 0;
}

JavaScript

function sortString(s) {
    let count = Array(26).fill(0);
    for (let char of s) {
        count[char.charCodeAt(0) - 97]++;
    }
    let result = [];
    while (result.length < s.length) {
        // Smallest to largest
        for (let i = 0; i < 26; i++) {
            if (count[i] > 0) {
                result.push(String.fromCharCode(i + 97));
                count[i]--;
            }
        }
        // Largest to smallest
        for (let i = 25; i >= 0; i--) {
            if (count[i] > 0) {
                result.push(String.fromCharCode(i + 97));
                count[i]--;
            }
        }
    }
    return result.join('');
}

let s = "rat";
console.log(sortString(s));

#include <stdio.h>
#include <string.h>

char* sortString(char* s) {
    int count[26] = {0};
    int len = strlen(s);
    for (int i = 0; i < len; i++)
        count[s[i] - 'a']++;
    
    char* result = (char*) malloc((len + 1) * sizeof(char));
    int index = 0;
    while (index < len) {
        // Smallest to largest
        for (int i = 0; i < 26; i++) {
            if (count[i] > 0) {
                result[index++] = i + 'a';
                count[i]--;
            }
        }
        // Largest to smallest
        for (int i = 25; i >= 0; i--) {
            if (count[i] > 0) {
                result[index++] = i + 'a';
                count[i]--;
            }
        }
    }
    result[index] = '\0';
    return result;
}

int main() {
    char s[] = "aaaabbbbcccc";
    char* result = sortString(s);
    printf("%s\n", result);
    free(result);
    return 0;
}

using System;

class Solution {
    public string SortString(string s) {
        int[] count = new int[26];
        foreach (char c in s)
            count[c - 'a']++;
        char[] result = new char[s.Length];
        int index = 0;
        while (index < s.Length) {
            // Smallest to largest
            for (int i = 0; i < 26; i++) {
                if (count[i] > 0) {
                    result[index++] = (char)(i + 'a');
                    count[i]--;
                }
            }
            // Largest to smallest
            for (int i = 25; i >= 0; i--) {
                if (count[i] > 0) {
                    result[index++] = (char)(i + 'a');
                    count[i]--;
                }
            }
        }
        return new string(result);
    }

    static void Main() {
        Solution sol = new Solution();
        Console.WriteLine(sol.SortString("aaaabbbbcccc"));
    }
}

The Python solution utilizes a list to maintain frequencies of each letter. As we loop through this list, append applicable characters in ascending and descending order, continuing until the result is equal to the original size of the string.

Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Try this approach in the editor

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.

Python

def sortString(s):
    sorted_s = sorted(s)
    result = []
    start = 0
    end = len(sorted_s) - 1
    forward = True
    while start <= end:
        if forward:
            result.append(sorted_s[start])
            start += 1
        else:
            result.append(sorted_s[end])
            end -= 1
        forward = not forward
    return ''.join(result)

s = "rat"
print(sortString(s))

Java

import java.util.Arrays;

public class Main {
    public static String sortString(String s) {
        char[] arr = s.toCharArray();
        Arrays.sort(arr);
        StringBuilder result = new StringBuilder();
        int start = 0, end = arr.length - 1;
        boolean forward = true;
        while (start <= end) {
            if (forward) {
                result.append(arr[start++]);
            } else {
                result.append(arr[end--]);
            }
            forward = !forward;
        }
        return result.toString();
    }

    public static void main(String[] args) {
        String s = "rat";
        System.out.println(sortString(s));
    }
}

C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

string sortString(string s) {
    sort(s.begin(), s.end());
    string result;
    int start = 0, end = s.size() - 1;
    bool forward = true;
    while (start <= end) {
        if (forward) {
            result += s[start++];
        } else {
            result += s[end--];
        }
        forward = !forward;
    }
    return result;
}

int main() {
    string s = "rat";
    cout << sortString(s) << endl;
    return 0;
}

JavaScript

function sortString(s) {
    let sortedArray = [...s].sort();
    let result = [];
    let start = 0, end = sortedArray.length - 1;
    let forward = true;
    while (start <= end) {
        if (forward) {
            result.push(sortedArray[start++]);
        } else {
            result.push(sortedArray[end--]);
        }
        forward = !forward;
    }
    return result.join('');
}

let s = "rat";
console.log(sortString(s));

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compareChar(const void* a, const void* b) {
    return (*(char*)a - *(char*)b);
}

char* sortString(char* s) {
    int len = strlen(s);
    qsort(s, len, sizeof(char), compareChar);
    char* result = (char*) malloc((len + 1) * sizeof(char));
    int start = 0, end = len - 1, index = 0;
    int inc = 1;
    while (start <= end) {
        if (inc) {
            result[index++] = s[start++];
        } else {
            result[index++] = s[end--];
        }
        inc = !inc;
    }
    result[index] = '\0';
    return result;
}

int main() {
    char s[] = "rat";
    char* result = sortString(s);
    printf("%s\n", result);
    free(result);
    return 0;
}

using System;

class Solution {
    public string SortString(string s) {
        char[] arr = s.ToCharArray();
        Array.Sort(arr);
        int start = 0, end = arr.Length - 1;
        bool forward = true;
        char[] result = new char[arr.Length];
        int index = 0;
        while (start <= end) {
            if (forward) {
                result[index++] = arr[start++];
            } else {
                result[index++] = arr[end--];
            }
            forward = !forward;
        }
        return new string(result);
    }

    static void Main() {
        Solution sol = new Solution();
        Console.WriteLine(sol.SortString("rat"));
    }
}

The Python code sorts the input string and uses a while loop and a toggle boolean to selectively choose characters from the boundaries of the sorted array, building the output result.

Complexity

Time Complexity: O(n log n)
Space Complexity: O(n)

Try this approach in the editor

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.

TypeScript

function sortString(s: string): string {
    const cnt: number[] = Array(26).fill(0);
    for (const c of s) {
        ++cnt[c.charCodeAt(0) - 'a'.charCodeAt(0)];
    }
    const ans: string[] = [];
    while (ans.length < s.length) {
        for (let i = 0; i < 26; ++i) {
            if (cnt[i]) {
                ans.push(String.fromCharCode(i + 'a'.charCodeAt(0)));
                --cnt[i];
            }
        }
        for (let i = 25; i >= 0; --i) {
            if (cnt[i]) {
                ans.push(String.fromCharCode(i + 'a'.charCodeAt(0)));
                --cnt[i];
            }
        }
    }
    return ans.join('');
}

func sortString(s string) string {
	cnt := [26]int{}
	for _, c := range s {
		cnt[c-'a']++
	}
	n := len(s)
	ans := make([]byte, 0, n)
	for len(ans) < n {
		for i := 0; i < 26; i++ {
			if cnt[i] > 0 {
				ans = append(ans, byte(i)+'a')
				cnt[i]--
			}
		}
		for i := 25; i >= 0; i-- {
			if cnt[i] > 0 {
				ans = append(ans, byte(i)+'a')
				cnt[i]--
			}
		}
	}
	return string(ans)
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Counting Sort Approach	Time Complexity: O(n) Space Complexity: O(1)
Two Pointers and Sorting Approach	Time Complexity: O(n log n) Space Complexity: O(n)
Counting + Simulation	–

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

Frequently asked questions

Is Increasing Decreasing String easy or hard?

Increasing Decreasing String is classified as an Easy problem on LeetCode with an acceptance rate above 75%. The challenge mainly involves recognizing that counting frequencies is more efficient than sorting for a fixed alphabet.

How to solve Increasing Decreasing String in O(n)?

Use a counting array to store the frequency of each lowercase character. Repeatedly iterate from 'a' to 'z' adding available characters, then iterate from 'z' to 'a'. Continue alternating until the output length equals the input string length. Since the alphabet size is constant, the total runtime becomes linear in the size of the string.

Increasing Decreasing String Python or Java solution?

Both Python and Java implementations typically use an integer array of size 26 to count character frequencies. The algorithm repeatedly scans forward and backward through the alphabet while appending characters to a result builder until all counts reach zero.

What is the best approach for Increasing Decreasing String?

The counting sort approach using a frequency array of size 26 is the most efficient solution. It repeatedly scans characters from 'a' to 'z' and then 'z' to 'a', appending available letters. Because the alphabet size is fixed, the algorithm runs in O(n) time with O(1) extra space.

What data structure is used in Increasing Decreasing String?

The optimal solution uses a frequency array (a simple counting hash structure) of size 26 to track occurrences of each character. This structure enables constant-time updates and ordered traversal of characters during the increasing and decreasing passes.

What is the time complexity of Increasing Decreasing String?

The optimal solution runs in O(n) time using a frequency array for the 26 lowercase letters. Each character is processed a constant number of times during forward and backward passes. Space complexity is O(1) because the frequency array size is fixed.

Is Increasing Decreasing String asked at Google, Amazon, or Meta?

Problems of this pattern frequently appear in interviews at large tech companies because they test string manipulation and counting techniques. Variants of frequency-based string reconstruction have appeared in interviews at companies like Amazon and Google.

Increasing Decreasing String solution and explanation

The problem

Approach overview

Approach 1: Counting Sort Approach

Approach 2: Two Pointers and Sorting Approach

Approach 3: Counting + Simulation

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Increasing Decreasing String solution and explanation

The problem

Approach overview

Approach 1: Counting Sort Approach

Approach 2: Two Pointers and Sorting Approach

Approach 3: Counting + Simulation

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems