Scale Engineer

Increasing Decreasing String

Easy
#1270Time: O(N^2). The initial sort takes O(N log N). The main `while` loop runs until `count` reaches `N`. In each iteration of the `while` loop, we perform two full scans of the `chars` array, each taking O(N) time. The number of `while` loop iterations can be up to O(N) in some cases, leading to a total time complexity dominated by the nested loops, resulting in O(N^2).Space: O(N). We need O(N) space for the character array `chars` and the boolean `visited` array. The `StringBuilder` also uses O(N) space for the result.1 company
Patterns
Counting
Data structures
Hash TableString
Companies
Akuna Capital

Prompt

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

  1. Remove the smallest character from s and append it to the result.
  2. Remove the smallest character from s that is greater than the last appended character, and append it to the result.
  3. Repeat step 2 until no more characters can be removed.
  4. Remove the largest character from s and append it to the result.
  5. Remove the largest character from s that is smaller than the last appended character, and append it to the result.
  6. Repeat step 5 until no more characters can be removed.
  7. 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.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly simulates the described algorithm. It first sorts the input string to make finding the next smallest/largest character easier. It then uses a visited array to keep track of which characters have already been added to the result. The process involves repeatedly scanning the sorted array forwards and backwards to pick characters according to the rules, until all characters are used.

Algorithm

  • Convert the input string s into a character array chars.
  • Sort the chars array in ascending order.
  • Initialize a boolean array visited of size n (length of s) to all false.
  • Initialize an empty StringBuilder named result to store the final string.
  • Initialize a counter count to 0 to keep track of the number of characters added to result.
  • Start a loop that continues as long as count < n:
    • Increasing Pass:
      • Initialize a lastChar variable to a value smaller than any possible character (e.g., (char)0).
      • Iterate through the chars array from index 0 to n-1.
      • For each character chars[i], if it has not been visited (!visited[i]) and is strictly greater than lastChar, append it to result, mark it as visited (visited[i] = true), update lastChar to chars[i], and increment count.
    • Decreasing Pass:
      • Initialize lastChar to a value larger than any possible character (e.g., (char)127).
      • Iterate through the chars array from index n-1 down to 0.
      • For each character chars[i], if it has not been visited (!visited[i]) and is strictly smaller than lastChar, append it to result, mark it as visited, update lastChar, and increment count.
  • After the loop terminates, convert the result StringBuilder to a string and return it.

Walkthrough

The core idea is to mimic the process step-by-step. First, we convert the input string s into a character array and sort it. This helps in iterating through characters in a naturally ordered way. We use a boolean array visited of the same size as the string to mark characters that have been appended to the result, preventing them from being used again.

The process continues in a loop until all characters are used (i.e., the result string's length equals the input string's length).

Inside the loop, we perform two passes:

  1. Increasing Pass: We iterate through the sorted character array from left to right. We look for the first unvisited character and append it. Then, we continue scanning for the next unvisited character that is strictly greater than the one just appended. We repeat this until we can't find any more characters in this pass.
  2. Decreasing Pass: We iterate through the sorted character array from right to left. We find the first unvisited character and append it. Then, we scan backwards for the next unvisited character that is strictly smaller than the one just appended. This continues until the pass is complete.

These two passes are repeated until all characters from the original string are placed in the result.

import java.util.Arrays; class Solution {    public String sortString(String s) {        char[] chars = s.toCharArray();        Arrays.sort(chars);        int n = s.length();        boolean[] visited = new boolean[n];        StringBuilder result = new StringBuilder();        int count = 0;         while (count < n) {            // Increasing pass            char lastChar = 0; // Placeholder smaller than any char            for (int i = 0; i < n; i++) {                if (!visited[i] && chars[i] > lastChar) {                    result.append(chars[i]);                    visited[i] = true;                    lastChar = chars[i];                    count++;                }            }             // Decreasing pass            lastChar = 127; // Placeholder larger than any char            for (int i = n - 1; i >= 0; i--) {                if (!visited[i] && chars[i] < lastChar) {                    result.append(chars[i]);                    visited[i] = true;                    lastChar = chars[i];                    count++;                }            }        }        return result.toString();    }}

Complexity

Time

O(N^2). The initial sort takes O(N log N). The main `while` loop runs until `count` reaches `N`. In each iteration of the `while` loop, we perform two full scans of the `chars` array, each taking O(N) time. The number of `while` loop iterations can be up to O(N) in some cases, leading to a total time complexity dominated by the nested loops, resulting in O(N^2).

Space

O(N). We need O(N) space for the character array `chars` and the boolean `visited` array. The `StringBuilder` also uses O(N) space for the result.

Trade-offs

Pros

  • The logic is a direct translation of the problem statement, making it relatively easy to conceptualize.

Cons

  • The time complexity of O(N^2) is inefficient and may be too slow for larger constraints, although it passes for N <= 500.

  • It involves repeated full scans of the character array, which is redundant work.

Solutions

class Solution {public  String sortString(String s) {    int[] cnt = new int[26];    int n = s.length();    for (int i = 0; i < n; ++i) {      cnt[s.charAt(i) - 'a']++;    }    StringBuilder sb = new StringBuilder();    while (sb.length() < n) {      for (int i = 0; i < 26; ++i) {        if (cnt[i] > 0) {          sb.append((char)('a' + i));          --cnt[i];        }      }      for (int i = 25; i >= 0; --i) {        if (cnt[i] > 0) {          sb.append((char)('a' + i));          --cnt[i];        }      }    }    return sb.toString();  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem