algoadvance

LeetCode Problem 1544: Make The String Great

Description: Given a string s of lower and upper case English letters.

A string is called great if it is empty or if there are no two adjacent characters x and y such that:

• x is a lowercase letter and y is the same letter but in uppercase (or vice versa).

To make the string great, you can choose two adjacent characters that make the string not great and remove them. You can keep doing this until the string becomes great.

Return the string after making it great. The returned string should be in lowercase.

Clarifying Questions

1. Input constraints:
   • Can the string s be empty?
     • Yes, the string s can be empty.
2. Output constraints:
   • What should be the case of the output string?
     • The problem doesn’t specify changing the case of the final string except to remove conflicting pairs. Outputs in the original case retained unless removed.
3. Occurence of non-alphabet characters:
   • Are there any non-alphabet characters in the string?
     • No, the string contains only lower and upper case English letters.

Strategy

To solve this problem, we need to process the string and eliminate pairs of adjacent characters where one is the lowercase equivalent of the other in uppercase. We can utilize a stack to manage this in an efficient manner.

1. Initialize an empty stack.
2. Iterate through each character in the string:
   • If the stack is not empty and the top of the stack forms a problematic pair with the current character (one is the lowercase version of the other in uppercase), pop the character from the stack.
   • Otherwise, push the current character onto the stack.
3. Convert the stack back to a string and return it.

This approach ensures we process the string in one pass with efficient removal and addition operations using the stack.

Time Complexity

• Time Complexity: O(n), where n is the length of the string. Each character is processed exactly once on a single traversal.
• Space Complexity: O(n), in the worst case, the stack could store all characters, such as when there are no removable pairs.

Code

def makeGood(s: str) -> str:
    stack = []
    for char in s:
        if stack and ((char.islower() and stack[-1] == char.upper()) or (char.isupper() and stack[-1] == char.lower())):
            stack.pop()  # Remove the problematic pair
        else:
            stack.append(char)  # Add current character to the stack

    return ''.join(stack)

# Example usage
s = "leEeetcode"
print(makeGood(s))  # Output: "leetcode"

This code uses a stack to dynamically manage conflicts between adjacent characters and ensures the resultant string is “great” as per the given criteria.

Try our interview co-pilot at AlgoAdvance.com

• 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?