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

Make The String Great

Difficulty: Easy

Problem Description

Given a string s of lower and upper case English letters, a good string is one that does not have two adjacent characters where one is the lowercase version of a letter and the other is the uppercase version of the same letter. You can remove such adjacent characters until the string becomes good. Return the resulting good string.

Key Insights

  • A good string does not have adjacent characters that are the same letter in different cases.
  • Removing pairs of adjacent characters can be efficiently managed using a stack.
  • The stack allows us to keep track of the characters and easily remove the last character if the current character and the top of the stack form a bad pair.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

The problem can be solved using a stack data structure. The idea is to iterate through each character in the string. For each character, we check if it forms a bad pair with the character at the top of the stack. If it does, we pop the stack; otherwise, we push the current character onto the stack. Finally, we join the characters in the stack to form the resulting good string.

Code Solutions

def makeGood(s: str) -> str:
    stack = []
    for char in s:
        # Check if the stack is not empty and the current character forms a bad pair with the top of the stack
        if stack and (stack[-1].swapcase() == char):
            stack.pop()  # Remove the last character from the stack
        else:
            stack.append(char)  # Add the current character to the stack
    return ''.join(stack)  # Join the stack to form the resulting string
← Back to All Questions