Maximum Value from Removing Rare Items - codepath/compsci_guides GitHub Wiki

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 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.
• Q: What is the output?
  • A: The output is an integer representing the maximum value that can be gained after removing the pairs "AB" and "BA" according to the given rules.
• Q: How do the operations work?
  • A: You can repeatedly remove the pair "AB" to gain x points and the pair "BA" to gain y points until no more pairs can be removed.

P-lan

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

• Not correctly handling the order of removal, which could result in a suboptimal score.
• Failing to process the remaining string after the first removal operation.

I-mplement

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