LeetCode 1370: Increasing Decreasing String Solution

Master LeetCode problem 1370 (Increasing Decreasing String), a easy challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1370. Increasing Decreasing String

Easy

Hash Table String Counting

Problem Explanation

Explanation:

This problem requires us to reorder a given string according to a specific algorithm. We need to repeatedly find the smallest and largest characters from the remaining string and append them to the result string in a specific order. We continue this process until all characters are used.

To solve this problem, we can follow these steps:

Count the occurrences of each character in the input string.
Create a result string to store the reordered characters.
Loop through the characters in ascending order until the result string is the same length as the input string:
- Find and append the smallest character that has remaining occurrences.
- Find and append the smallest character greater than the last appended character.
- Find and append the largest character that has remaining occurrences.
- Find and append the largest character smaller than the last appended character.
Return the result string.

The time complexity of this solution is O(n^2) where n is the length of the input string. The space complexity is O(1) since we are using a fixed-size array to count character occurrences.

Solution Code

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

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1370 (Increasing Decreasing String)?

This page provides optimized solutions for LeetCode problem 1370 (Increasing Decreasing String) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1370 (Increasing Decreasing String)?

The time complexity for LeetCode 1370 (Increasing Decreasing String) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1370 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1370 in Java, C++, or Python.

Back to LeetCode Solutions