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.
items
representing a collection of mystical items, and two integers x
and y
representing the value points gained by removing pairs "AB"
and "BA"
, respectively."AB"
and "BA"
according to the given rules."AB"
to gain x
points and the pair "BA"
to gain y
points until no more pairs can be removed.Plan the solution with appropriate visualizations and pseudocode.
General Idea: Since the removal of "AB"
and "BA"
pairs is independent but the total value depends on the order of removal, you should first remove the pair that yields the higher value. After removing the first pair, you can remove the other pair in the remaining string.
1. Define a helper function `remove_and_score` that:
1. Iterates through the string `s`.
2. Uses a stack to track characters.
3. Removes a specified pair (either `"AB"` or `"BA"`) whenever it is encountered and adds the corresponding score.
4. Returns the total points gained and the remaining string after removals.
2. Compare `x` and `y`:
1. If `x > y`, first remove `"AB"` pairs, then remove `"BA"` pairs from the remaining string.
2. If `y > x`, first remove `"BA"` pairs, then remove `"AB"` pairs from the remaining string.
3. Return the sum of the points gained from both operations.
⚠️ Common Mistakes
def maximum_value(items, x, y):
def remove_and_score(s, first, second, score):
stack = []
points = 0
s.upper()
for char in s:
if stack and stack[-1] == first and char == second:
stack.pop()
points += score
else:
stack.append(char)
return points, ''.join(stack)
if x > y:
# Remove "AB" first and then "BA"
points, remaining = remove_and_score(items, 'A', 'B', x)
points2, _ = remove_and_score(remaining, 'B', 'A', y)
else:
# Remove "BA" first and then "AB"
points, remaining = remove_and_score(items, 'B', 'A', y)
points2, _ = remove_and_score(remaining, 'A', 'B', x)
return points + points2
# Example usage
s1 = "cdbcbbaaabab"
x1, y1 = 4, 5
print(maximum_value(s1, x1, y1)) # Output: 19
s2 = "aabbaaxybbaabb"
x2, y2 = 5, 4
print(maximum_value(s2, x2, y2)) # Output: 20