We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Increasing Decreasing String

Difficulty: Easy

Problem Description

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.

Key Insights

  • The problem requires knowledge of character ordering and manipulation.
  • We need to repeatedly find the smallest and largest characters in a string while maintaining their order.
  • The algorithm has a cyclic nature, alternating between increasing and decreasing sequences.

Space and Time Complexity

Time Complexity: O(n log n), where n is the length of the string, due to sorting characters. Space Complexity: O(n), for storing the frequency of characters.

Solution

To solve the problem, we will:

  1. Count the frequency of each character using a frequency array.
  2. Construct the result string by alternating between the smallest and largest characters.
  3. Use two pointers or a simple loop to append characters in the required order until all characters are processed.

The key data structure used here is an array to keep track of character counts, allowing us to efficiently retrieve the smallest and largest characters.

Code Solutions

def sortString(s: str) -> str:
    from collections import Counter
    
    # Count the frequency of each character
    char_count = Counter(s)
    result = []
    
    while char_count:
        # Step 1: Append the smallest characters
        for char in sorted(char_count.keys()):
            result.append(char)
            char_count[char] -= 1
            if char_count[char] == 0:
                del char_count[char]
        
        # Step 2: Append the largest characters
        for char in sorted(char_count.keys(), reverse=True):
            result.append(char)
            char_count[char] -= 1
            if char_count[char] == 0:
                del char_count[char]
    
    return ''.join(result)
← Back to All Questions