TIP102 Unit 3 Session 2 Advanced (Click for link to problem statements)
Understand what the interviewer is asking for by using test cases and questions about the problem.
s
of even length n
, containing exactly n / 2
left walls '['
and n / 2
right walls ']'
.Plan the solution with appropriate visualizations and pseudocode.
General Idea: Track the imbalance between left and right walls as you iterate through the string. When the imbalance exceeds what is currently balanced, you will need to swap walls. The goal is to minimize the imbalance and determine the minimum number of swaps needed.
1. Initialize variables `imbalance` and `max_imbalance` to 0.
2. Iterate through each character in the string `s`:
1. If the character is a left wall '[', decrease the `imbalance` by 1.
2. If the character is a right wall ']', increase the `imbalance` by 1.
3. Update `max_imbalance` to the maximum of `max_imbalance` and `imbalance`.
3. The minimum number of swaps required is given by `(max_imbalance + 1) // 2`.
4. Return the result.
⚠️ Common Mistakes
def min_swaps(s):
imbalance = 0
max_imbalance = 0
for char in s:
if char == '[':
imbalance -= 1
else:
imbalance += 1
max_imbalance = max(max_imbalance, imbalance)
return (max_imbalance + 1) // 2
# Example usage
print(min_swaps("][][")) # Output: 1
print(min_swaps("]]][[[")) # Output: 2
print(min_swaps("[]")) # Output: 0