We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Score From Removing Substrings

Number: 1818

Difficulty: Medium

Paid? No

Companies: Bloomberg, Google

Problem Description

Given a string s and two integer values x and y, you can repeatedly remove either the substring "ab" to earn x points or the substring "ba" to earn y points. Your task is to determine the maximum total points you can obtain by strategically performing these removals on s.

Key Insights

  • The order of removal matters because once a substring is removed, the remaining parts of the string can combine to form new removable pairs.
  • It is optimal to first remove the substring with the higher reward. This prevents potentially losing higher points if a higher rewarded pair is formed later.
  • Use a greedy approach with a stack to efficiently remove substrings in one pass.
  • Process the string twice:
    • First pass: Remove the higher-value substring while using a stack to track characters.
    • Second pass: On the resulting string, remove the lower-value substring.

Space and Time Complexity

Time Complexity: O(n) per pass, hence overall O(n).
Space Complexity: O(n) in worst-case scenario for the stack.

Solution

We use a greedy algorithm with stacks:

  1. Determine which substring removal gives more points.
  2. For the substring with higher reward:
    • Traverse the string, using a stack to check if the current character and the top of the stack form the high-reward pair.
    • If they do, pop from the stack and add the respective points.
  3. For the remaining substring, repeat a similar process using a new stack.
  4. Sum the points from both passes to get the maximum score.

This approach ensures that we remove the most valuable pairs first without missing any formation of the less valuable pair later.

Code Solutions

# Python solution with detailed comments
def maximumGain(s: str, x: int, y: int) -> int:
    total_points = 0

    # Decide which pair to remove first based on their points
    if x >= y:
        first_pair, first_score = "ab", x
        second_pair, second_score = "ba", y
    else:
        first_pair, first_score = "ba", y
        second_pair, second_score = "ab", x

    # First pass: remove first_pair using a greedy stack approach
    stack = []
    remaining_chars = []
    for char in s:
        if stack and (stack[-1] + char == first_pair):
            stack.pop()  # Remove the matching pair from the stack
            total_points += first_score  # Add score for this removal
        else:
            stack.append(char)
    # The characters remaining after first pass
    remaining_chars = stack

    # Second pass: remove second_pair from the remaining characters
    stack = []
    for char in remaining_chars:
        if stack and (stack[-1] + char == second_pair):
            stack.pop()  # removal of second pair
            total_points += second_score
        else:
            stack.append(char)

    return total_points

# Example usage:
s = "cdbcbbaaabab"
x = 4
y = 5
print(maximumGain(s, x, y))  # Expected output: 19
← Back to All Questions