# Increasing Decreasing String
**Difficulty:** EASY
[External](https://leetcode.com/problems/increasing-decreasing-string)
Canonical: https://scaleengineer.com/dsa/problems/increasing-decreasing-string
**Patterns:** [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Data structures:** Hash Table, String
**Companies:** [Akuna Capital](https://scaleengineer.com/companies/akuna-capital)
---
## Problem
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
## Brute-Force Simulation with Sorting
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.
**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.
**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.
### Explanation
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.

```java
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();
    }
}
```
### 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.

## Optimized Approach using Frequency Array
A much more efficient approach utilizes a frequency map to store the counts of each character. Since the input string consists of only lowercase English letters, a simple integer array of size 26 can serve as this frequency map. The algorithm then repeatedly iterates through this frequency array, first forwards (from 'a' to 'z') and then backwards (from 'z' to 'a'), appending characters to the result as long as their count is greater than zero. This continues until the result string is the same length as the input string.
**Time:** O(N). The initial frequency counting takes O(N) time. The `while` loop runs as many times as the maximum frequency of any character. In each iteration of the `while` loop, we iterate through the 26-element `counts` array twice. The total time is O(N + max_freq * 26). Since `max_freq <= N` and 26 is a constant, this simplifies to O(N). · **Space:** O(1). We use a constant amount of extra space for the `counts` array (size 26). The space for the result `StringBuilder` is O(N), but this is typically excluded from space complexity analysis as it's the output.
**Pros:** Highly efficient with a linear time complexity of O(N).; Simple to implement and understand.; Effectively uses the problem constraint that the string only contains lowercase English letters.; Requires only constant extra space (excluding the output string).
**Cons:** This approach is optimized for a small, fixed-size character set. If the character set were very large or unbounded, a hash map would be needed, which could have slightly worse performance characteristics than a simple array.
### Explanation
This method avoids sorting and repeated scans of the entire dataset. Instead, it focuses on the counts of the 26 possible characters.

First, we create an integer array `counts` of size 26, initialized to zeros. We iterate through the input string `s` once to populate this array with the frequency of each character. `counts[0]` will store the count of 'a', `counts[1]` for 'b', and so on.

We use a `StringBuilder` to construct the result string.

The main part of the algorithm is a loop that continues as long as the length of our result string is less than the length of the original string `s`.

Inside the loop, we have two phases corresponding to the increasing and decreasing steps:
1.  **Increasing Pass:** We iterate from index 0 to 25 of our `counts` array. If the count at the current index `i` is positive, it means the character `(char)('a' + i)` is available. We append this character to our result, and decrement its count in the `counts` array.
2.  **Decreasing Pass:** We do the same, but iterate from index 25 down to 0. If a character's count is positive, we append it and decrement its count.

This process guarantees that in each pass, we pick characters in the specified order (smallest to largest, then largest to smallest) from the available pool. The loop terminates once all characters have been used up (i.e., all counts are zero and the result string has the desired length).

```java
class Solution {
    public String sortString(String s) {
        int[] counts = new int[26];
        for (char c : s.toCharArray()) {
            counts[c - 'a']++;
        }

        StringBuilder result = new StringBuilder();
        int n = s.length();

        while (result.length() < n) {
            // Increasing pass
            for (int i = 0; i < 26; i++) {
                if (counts[i] > 0) {
                    result.append((char) ('a' + i));
                    counts[i]--;
                }
            }

            // Decreasing pass
            for (int i = 25; i >= 0; i--) {
                if (counts[i] > 0) {
                    result.append((char) ('a' + i));
                    counts[i]--;
                }
            }
        }
        return result.toString();
    }
}
```
### Algorithm
*   Create an integer array `counts` of size 26, initialized to all zeros.
*   Iterate through the input string `s` and for each character `c`, increment the count at `counts[c - 'a']`.
*   Initialize an empty `StringBuilder` named `result`.
*   Start a loop that continues as long as the length of `result` is less than the length of `s`.
    *   **Increasing Pass:** Iterate `i` from `0` to `25`. If `counts[i]` is greater than 0, append the character `(char)('a' + i)` to `result` and decrement `counts[i]`.
    *   **Decreasing Pass:** Iterate `i` from `25` down to `0`. If `counts[i]` is greater than 0, append the character `(char)('a' + i)` to `result` and decrement `counts[i]`.
*   Once the loop finishes, convert `result` to a string and return it.

# Solutions
### Java

```java
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();
  }
}

```

### JavaScript

```javascript
/** * @param {string} s * @return {string} */ var sortString = function (s) {
  const cnt = Array(26).fill(0);
  for (const c of s) {
    ++cnt[c.charCodeAt(0) - " a ".charCodeAt(0)];
  }
  const ans = [];
  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("");
};

```

### CPP

```cpp
class Solution {
public:
  string sortString(string s) {
    int cnt[26]{};
    for (char &c : s) {
      ++cnt[c - 'a'];
    }
    string ans;
    while (ans.size() < s.size()) {
      for (int i = 0; i < 26; ++i) {
        if (cnt[i]) {
          ans += i + 'a';
          --cnt[i];
        }
      }
      for (int i = 25; i >= 0; --i) {
        if (cnt[i]) {
          ans += i + 'a';
          --cnt[i];
        }
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def sortString(self, s: str) -> str: cnt = Counter(s) cs = ascii_lowercase + ascii_lowercase[:: - 1] ans = [] while len(ans) < len(s): for c in cs: if cnt[c]: ans . append(c) cnt[c] -= 1 return "" . join(ans)

```