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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Increasing Decreasing String

Number: 1472

Difficulty: Easy

Paid? No

Companies: Akuna Capital

Problem Description

Given a string s, you are to reorder it by repeatedly appending the smallest available character (and subsequently the smallest character greater than the last appended) until no more characters can be taken, then appending the largest available character (and similarly the largest character smaller than the last appended) until you cannot select more. This process is repeated until all characters from s have been used.

Key Insights

  • Use a frequency count (e.g., an array of size 26) to keep track of available characters.
  • Since the available characters are only lowercase letters, iterating over them in increasing or decreasing order is efficient (constant 26 steps).
  • The algorithm simulates the given process in rounds; each round consists of an increasing pass followed by a decreasing pass.
  • The overall iteration continues until the resultant string has the same length as the input.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1) (since the frequency array always has 26 elements)

Solution

To solve the problem, first count the frequency of each character in s using an array of size 26. Then, iterate while the result string has not reached the length of s. In each iteration, perform an increasing pass by scanning from 'a' to 'z' and appending each available character, then perform a decreasing pass by scanning from 'z' to 'a'. Remove characters as they are appended by decrementing their corresponding count. This simulation ensures that the specific order defined by the algorithm is maintained.

Code Solutions

# Define the function to sort the string based on the described algorithm
def sortString(s):
    # Initialize a frequency list for each lowercase letter
    freq = [0] * 26
    for char in s:
        freq[ord(char) - ord('a')] += 1

    result = []  # List to store the result characters

    # Continue until the result list length equals the input string length
    while len(result) < len(s):
        # Increasing order pass: iterate from 'a' to 'z'
        for i in range(26):
            if freq[i] > 0:
                result.append(chr(i + ord('a')))  # Append the character
                freq[i] -= 1  # Decrement its frequency
        # Decreasing order pass: iterate from 'z' to 'a'
        for i in range(25, -1, -1):
            if freq[i] > 0:
                result.append(chr(i + ord('a')))  # Append the character
                freq[i] -= 1  # Decrement its frequency

    # Convert the list of characters back to a string
    return ''.join(result)

# Example usage:
# print(sortString("aaaabbbbcccc"))
← Back to All Questions