Minimum Remaining Watchlist After Removing Movies

Edit PagePage History

TIP102 Unit 3 Session 1 Standard (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 watchlist consisting of uppercase English letters, where each letter represents a movie.
• Q: What is the output?
  • A: The output is the minimum possible length of the resulting watchlist after removing all possible occurrences of the movie pairs "AB" or "CD".
• Q: How should the movie pairs "AB" and "CD" be removed?
  • A: Continuously remove any "AB" or "CD" pairs from the watchlist until no such pairs remain.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use a stack to remove the movie pairs "AB" or "CD" as they appear, and return the length of the remaining watchlist.

1. Initialize an empty stack to keep track of the movies in the watchlist.
2. Iterate through each character in the `watchlist`:
   1. If the stack is not empty and the top of the stack forms a pair "AB" or "CD" with the current character, pop the stack (remove the pair).
   2. Otherwise, push the current character onto the stack.
3. After processing the entire watchlist, the stack will contain the remaining movies.
4. Return the length of the stack as the minimum possible length of the remaining watchlist.

⚠️ Common Mistakes

• Forgetting to continue checking for new "AB" or "CD" pairs after removing a pair.
• Mishandling cases where multiple consecutive pairs are present.
• Not correctly managing the stack operations, leading to incorrect results.

I-mplement

def min_remaining_watchlist(watchlist):
    stack = []

    for char in watchlist:
        if stack and ((stack[-1] == 'A' and char == 'B') or (stack[-1] == 'C' and char == 'D')):
            stack.pop()  # Remove the matching pair
        else:
            stack.append(char)  # Add the current movie to the stack

    return len(stack)