Maximum Score From Removing Substrings

Problem Statement

Given a string s along with two integers x and y, you have the ability to perform two types of substring removal operations to accumulate points. You can repeatedly remove the substring "ab" from s to gain x points or remove the substring "ba" to gain y points. Each time a substring is removed, the string s is shortened, and substrings cannot be overlapped during a single operation. The goal is to determine the maximum number of points that can be accumulated by applying these removal operations appropriately on the string s.

Examples

Example 1

Input:

s = "cdbcbbaaabab", x = 4, y = 5

Output:

19

Explanation:

- Remove the "ba" underlined in "cdbcbbaaabab". Now, s = "cdbcbbaaab" and 5 points are added to the score.
- Remove the "ab" underlined in "cdbcbbaaab". Now, s = "cdbcbbaa" and 4 points are added to the score.
- Remove the "ba" underlined in "cdbcbbaa". Now, s = "cdbcba" and 5 points are added to the score.
- Remove the "ba" underlined in "cdbcba". Now, s = "cdbc" and 5 points are added to the score.
Total score = 5 + 4 + 5 + 5 = 19.

Example 2

Input:

s = "aabbaaxybbaabb", x = 5, y = 4

Output:

20

Constraints

• 1 <= s.length <= 105
• 1 <= x, y <= 104
• s consists of lowercase English letters.

Approach and Intuition

1. Understanding the Problem Constraints:

   • The length of the string can be quite large, up to 105 characters. This implies that a highly optimized approach is necessary to avoid timeout errors.
   • The operations can be performed any number of times, which suggests the possibility of intricate looping or recursive solutions, possibly augmented with memoization.

2. Optimizing the Order of Operations:

   • Since removing one type of substring might create new opportunities to remove the other type, the order in which substrings are removed can affect the total score.
   • The intuitive approach could be to always remove the substring that offers the higher points first. However, this may not always yield the maximum total points due to the dynamic nature of the remaining string after each operation.

3. Approach to Solution:

   • One potential method to tackle the problem could be to perform a greedy approach:
     • Parse through the string while maintaining a count of possible "ab" and "ba" substrings.
     • Depending on which operation yields more points (x vs y), prioritize its removal.
     • Adjust the counts of "ab" and "ba" substrings dynamically as the string changes with each removal.
   • Another approach could be dynamic programming:
     • Define states that represent the maximum score attainable from the first i characters of s.
     • Use transition states based on whether an "ab" or "ba" is removed, and compute the maximum possible points from prior states.

4. Edge Cases & Considerations:

   • If x equals y, one might simplify the solution by always opting for the first removable substring found in any scan of s.
   • Consider the case where no "ab" or "ba" substrings exist; the score would then be 0.
   • What if the string has overlapping substrings like "aba" - determining which removal leads to the best outcome would be key.

This solution needs to be implemented while ensuring time complexity is kept as efficient as possible to handle the upper constraint of the input size.

Solutions

class Solution {
public:
    int maxScore(string str, int p, int q) {
        // Invert values if p < q to prioritize higher score
        if (p < q) {
            swap(p, q);
            reverse(str.begin(), str.end());
        }
    
        int countA = 0, countB = 0, score = 0;
    
        for (char c : str) {
            if (c == 'a') {
                ++countA;
            } else if (c == 'b') {
                if (countA > 0) {
                    --countA;
                    score += p;
                } else {
                    ++countB;
                }
            } else {
                // Handle sequences of 'a's and 'b's
                score += min(countB, countA) * q;
                countA = countB = 0;
            }
        }
        // Add scores for remaining pairs
        score += min(countB, countA) * q;
    
        return score;
    }
};