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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum Score From Removing Substrings

Difficulty: Medium

Problem Description

You are given a string s and two integers x and y. You can perform two types of operations any number of times. Remove substring "ab" and gain x points, or remove substring "ba" and gain y points. Return the maximum points you can gain after applying the above operations on s.

Key Insights

  • The problem involves removing specific substrings to maximize points.
  • The order of removals can affect the total score, as removing one type of substring may create opportunities for removing the other type.
  • A greedy approach can be beneficial, but careful tracking of the state of the string is necessary.
  • Using a stack can help manage the characters and efficiently determine when to remove "ab" or "ba".

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string s. Each character is processed once. Space Complexity: O(n), for the stack used to manage the characters.

Solution

To solve the problem, we can use a stack to process the string character by character. We will maintain the stack to track the current state of the string as we evaluate potential removals of "ab" and "ba".

  1. Traverse each character in the string:
    • If the stack is not empty and the current character along with the top of the stack forms "ab", pop the top of the stack and add x points to the score.
    • If the stack is not empty and the current character along with the top of the stack forms "ba", pop the top of the stack and add y points to the score.
    • If neither condition is met, push the current character onto the stack.
  2. Continue this process until all characters are processed.
  3. The score accumulated will be the maximum points obtainable.

Code Solutions

def maximumScore(s: str, x: int, y: int) -> int:
    stack = []
    score = 0
    
    for char in s:
        if stack and stack[-1] == 'a' and char == 'b':
            stack.pop()  # Remove "ab"
            score += x
        elif stack and stack[-1] == 'b' and char == 'a':
            stack.pop()  # Remove "ba"
            score += y
        else:
            stack.append(char)
    
    return score
← Back to All Questions