Designing a Balanced Room

TIP102 Unit 3 Session 2 Advanced (Click for link to problem statements)

U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Q: What is the input to the problem?
  • A: The input is a string s consisting of walls '(', ')', and lowercase English letters representing decorations.
• Q: What is the output?
  • A: The output is a string representing a balanced room layout, where the minimum number of walls '(' or ')' has been removed.
• Q: What defines a balanced room layout?
  • A: A room layout is balanced if it contains only decorations, or can be represented as concatenated valid layouts, or is enclosed by matching walls that form a valid layout.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use a stack to track unmatched walls. As you iterate through the string, ensure that each closing wall ')' has a corresponding opening wall '('. If a closing wall doesn't have a match, remove it. After the first pass, remove any unmatched opening walls '('.

1. Convert the string `s` into a list to allow modification.
2. Initialize an empty stack to keep track of unmatched opening walls `'('`.
3. Iterate through each character in the string:
   1. If the character is an opening wall `'('`, push its index onto the stack.
   2. If the character is a closing wall `')'`:
       - If the stack is not empty, pop an index from the stack (matching a pair of walls).
       - If the stack is empty (no matching opening wall), remove the current closing wall by setting its position in the list to an empty string.
4. After the iteration, remove any unmatched opening walls `'('` by setting their positions in the list to an empty string.
5. Return the modified string after joining the list back into a string.

⚠️ Common Mistakes

• Forgetting to remove all unmatched opening walls after the first pass.
• Incorrectly handling nested and adjacent walls, leading to an invalid balanced layout.

I-mplement

def make_balanced_room(s):
    stack = []
    s = list(s)

    for i, char in enumerate(s):
        if char == '(':
            stack.append(i)
        elif char == ')':
            if stack:
                stack.pop()
            else:
                s[i] = ''

    while stack:
        s[stack.pop()] = ''

    return ''.join(s)

# Example usage
print(make_balanced_room("art(t(d)e)s)ign)"))  # Output: "art(t(d)e)s)ign"
print(make_balanced_room("d)e(s)ign"))  # Output: "de(s)ign"
print(make_balanced_room(")("))  # Output: "