algoadvance

Leetcode 1370. Increasing Decreasing String

Problem Statement

Given a string s, you need to sort it in the following order:

1. Pick the smallest character from s which has not been picked yet. Append it to the result.
2. Pick the smallest character from s which has not been picked yet and append it to the result.
3. Repeat step 1 and step 2 until you cannot pick more characters from s.
4. Pick the largest character from s which has not been picked yet. Append it to the result.
5. Pick the largest character from s which has not been picked yet and append it to the result.
6. Repeat step 4 and step 5 until you cannot pick more characters from s.

You should combine the result of these steps to form the final resultant string.

Clarifying Questions

1. Is the input string s guaranteed to be non-empty?
2. Are there any constraints on the characters in the string (e.g., all lowercase)?
3. What should be the behavior if all characters are the same?
4. Should we consider any performance constraints?

Assuming:

1. The input string s contains only lowercase English letters.
2. The input size s is of reasonable length to fit within typical problem constraints on competitive programming platforms.

Strategy

1. Use an array of size 26 to count occurrences of each character in the string.
2. Use a boolean flag to switch between picking characters in increasing and decreasing order.
3. Create a loop that continues until no characters are left to pick.
4. Within the loop, if we are picking in increasing order, traverse our count array from ‘a’ to ‘z’ and pick each character while decreasing its count.
5. If we are picking in decreasing order, traverse our count array from ‘z’ to ‘a’ and pick each character while decreasing its count.
6. Append picked characters to the result string.
7. Flip the boolean flag at the end of each pass through the count array.
8. Continue until all characters are used up.

Code

#include <string>
#include <vector>

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

    std::string result;
    bool ascending = true;

    while(result.size() < s.size()) {
        if (ascending) {
            for (int i = 0; i < 26; ++i) {
                if (charCount[i] > 0) {
                    result.push_back('a' + i);
                    charCount[i]--;
                }
            }
        } else {
            for (int i = 25; i >= 0; --i) {
                if (charCount[i] > 0) {
                    result.push_back('a' + i);
                    charCount[i]--;
                }
            }
        }
        ascending = !ascending;
    }

    return result;
}

Time Complexity

• Time Complexity: O(n), where n is the length of string s.
  • Building the character count array takes O(n).
  • Constructing the result string involves iterating through a fixed number of character slots (26 for English lowercase letters) multiple times equal to the length of the string.
• Space Complexity: O(1), as the space used for the character count array is fixed at 26. The space for the result string can be considered O(n) but typically we focus on auxiliary space beyond the input and output.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?