1544. Make The String Great
Model: qwen2.5-coder:14b
Topics: String,Stack
FAANG asked: 1
Acceptance rate: 55.5%
Problem Breakdown
The problem requires us to transform a given string s into a “good” string by removing adjacent characters that are the same letter but in different cases (one lowercase and one uppercase). The goal is to return the final good string after all possible removals.
Inputs:
- A string
scontaining only lower and upper case English letters.
Outputs:
- A “good” string where no two adjacent characters are the same letter but in different cases.
Implicit Constraints or Tricky Edge Cases:
- The input string can be empty, which is trivially a good string.
- The input string could have all unique characters, meaning no removals are needed.
- The input string might require multiple passes to fully reduce to a good string.
Intuition
A brute-force approach would involve repeatedly scanning the string and removing adjacent bad pairs until no more can be found. This approach is inefficient because it may require multiple full scans of the string, leading to a time complexity of O(n^2).
The key insight is to use a stack data structure. By iterating through the string once, we can efficiently manage the removal of bad pairs by pushing characters onto the stack and popping them when a bad pair is encountered. This approach ensures that each character is processed only once, leading to an optimal time complexity.
Approach
- Initialize a Stack: Use a list as a stack to keep track of characters in the string.
- Iterate Through the String: For each character in the string:
- If the stack is not empty and the current character forms a bad pair with the top character of the stack (i.e., they are the same letter but in different cases), pop the top character from the stack.
- Otherwise, push the current character onto the stack.
- Construct the Result: After processing all characters, join the characters in the stack to form the final good string.
Complexity Analysis
- Time Complexity: O(n), where n is the length of the input string. Each character is processed at most twice (once pushed and once popped from the stack).
- Space Complexity: O(n) in the worst case, where no characters are removed and all are stored in the stack.
Solution
def makeGood(s: str) -> str:
stack = []
for char in s:
if stack and (char.swapcase() == stack[-1]):
stack.pop()
else:
stack.append(char)
return ''.join(stack)
Edge Cases Handled
- Empty String: The function returns an empty string, which is trivially good.
- All Unique Characters: If no bad pairs are found, the entire string remains in the stack and is returned as is.
- Multiple Removals Needed: The stack ensures that all possible bad pairs are removed in a single pass through the string.
The solution provided is correct, efficient, and clear. It handles all edge cases appropriately and adheres to the constraints given in the problem statement.