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.
chain
representing a sequence of magical item symbols."()"
represents a basic magical item with a power score of 1.AB
, where A
and B
are balanced chains, has a total power score of A + B
.(A)
, where A
is a balanced chain, has a power score of 2 * A
.Plan the solution with appropriate visualizations and pseudocode.
General Idea: Use a stack to keep track of the scores as you parse through the string. For every opening bracket, push a 0 onto the stack. For every closing bracket, pop the top value, calculate the score for the balanced substring, and update the stack.
1. Initialize a stack with a single element `0` to handle score calculation.
2. Iterate over each character in the string `chain`:
1. If the character is an opening bracket `'('`, push `0` onto the stack.
2. If the character is a closing bracket `')'`:
- Pop the top value from the stack.
- Calculate the score for the balanced substring:
- If the popped value is `0`, add `1` to the top value of the stack.
- Otherwise, double the popped value and add it to the top value of the stack.
3. The final result will be the only value left in the stack after processing the entire string.
4. Return the value from the stack as the total score.
⚠️ Common Mistakes
def score_of_mystical_market_chains(chain):
stack = [0] # Initialize the stack with a 0 to handle the score calculation
for char in chain:
if char == '(':
stack.append(0) # Push a 0 onto the stack to represent a new balanced substring
else:
v = stack.pop() # Pop the top element of the stack
stack[-1] += max(2 * v, 1) # Update the top element of the stack with the calculated score
return stack.pop() # The final result is the only element left in the stack
# Example usage
print(score_of_mystical_market_chains("()")) # Output: 1
print(score_of_mystical_market_chains("(())")) # Output: 2
print(score_of_mystical_market_chains("()()")) # Output: 2