1370. Increasing Decreasing String LeetCode Solution

Last updated: February 23, 2025

In this guide, you will get 1370. Increasing Decreasing String LeetCode Solution with the best time and space complexity. The solution to Increasing Decreasing String problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Increasing Decreasing String solution in C++
Increasing Decreasing String solution in Java
Increasing Decreasing String solution in Python
Additional Resources

1370. Increasing Decreasing String LeetCode Solution image

Problem Statement of Increasing Decreasing String

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.

Complexity Analysis

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

1370. Increasing Decreasing String LeetCode Solution in C++

class Solution {
 public:
  string sortString(string s) {
    string ans;
    vector<int> count(26);

    for (const char c : s)
      ++count[c - 'a'];

    while (ans.length() < s.size()) {
      for (int i = 0; i < 26; ++i) {
        if (count[i] == 0)
          continue;
        ans += 'a' + i;
        --count[i];
      }
      for (int i = 25; i >= 0; --i) {
        if (count[i] == 0)
          continue;
        ans += 'a' + i;
        --count[i];
      }
    }

    return ans;
  }
};
/* code provided by PROGIEZ */

1370. Increasing Decreasing String LeetCode Solution in Java

class Solution {
  public String sortString(String s) {
    StringBuilder sb = new StringBuilder();
    int[] count = new int[26];

    for (final char c : s.toCharArray())
      ++count[c - 'a'];

    while (sb.length() < s.length()) {
      for (int i = 0; i < 26; i++) {
        if (count[i] == 0)
          continue;
        sb.append((char) (i + 'a'));
        --count[i];
      }
      for (int i = 25; i >= 0; i--) {
        if (count[i] == 0)
          continue;
        sb.append((char) (i + 'a'));
        --count[i];
      }
    }

    return sb.toString();
  }
}
// code provided by PROGIEZ

1370. Increasing Decreasing String LeetCode Solution in Python

class Solution:
  def sortString(self, s: str) -> str:
    ans = []
    count = collections.Counter(s)

    while count:
      for chars in string.ascii_lowercase, reversed(string.ascii_lowercase):
        ans += [c for c in chars if c in count]
        count -= dict.fromkeys(count, 1)

    return ''.join(ans)
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents