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

Make The String Great

Number: 1666

Difficulty: Easy

Paid? No

Companies: Google, Adobe, Meta, Accenture

Problem Description

Given a string s containing both lower-case and upper-case English letters, remove any two adjacent characters that are the same letter with opposite cases (for example, 'a' and 'A') repeatedly until no such adjacent pair remains. Return the resulting "good" string (which might be empty).

Key Insights

  • Use a stack to efficiently check and eliminate adjacent conflicting characters.
  • For every character, compare with the top of the stack to decide if they form a conflicting pair.
  • Removing a pair might enable new pairs to form, but the stack approach naturally handles this.
  • The condition for removal can be checked using the difference in ASCII values (which is 32).

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string because we process each character once. Space Complexity: O(n) in the worst-case scenario when no characters are removed and the stack grows to size n.

Solution

We will iterate through the string using a stack. For each character, we check whether the stack is not empty and if the current character can form a pair with the top character on the stack. Two characters form a valid pair if they are the same letter in different cases. By recognizing that the ASCII difference between a lower-case and its corresponding upper-case letter is 32, we can easily check for this condition. If they match, we pop the top character from the stack; otherwise, we push the current character onto the stack. After processing the string, joining all characters from the stack gives the desired result.

Code Solutions

# Function to make the string "good" by removing adjacent conflicting pairs
def makeGood(s: str) -> str:
    # Create an empty list to use as a stack for characters
    stack = []
    # Iterate over each character in the input string
    for char in s:
        # Check if the stack is not empty and if the current character and the top of the stack form a conflicting pair
        if stack and abs(ord(char) - ord(stack[-1])) == 32:
            # Pop the top character as both cancel each other out
            stack.pop()
        else:
            # Otherwise, push the current character onto the stack
            stack.append(char)
    # Join the stack to form the final "good" string and return it
    return ''.join(stack)

# Example usage:
# print(makeGood("leEeetcode"))
← Back to All Questions