Maximum Score From Removing Substrings - Solution & Explanation

In this approach, we prioritize removing the substring with a higher score first. We utilize a stack to efficiently traverse and remove substrings from the string. Given two substrings 'ab' and 'ba', and their scores x and y, we decide which to remove first based on the higher score. The stack helps in processing the string in a single pass, adding character by character and checking for the target substring ending each time.

This solution leverages a stack to remove 'ab' or 'ba' substrings based on their point values. The approach consists of two sweeps across the input string: one for the highest point substring and another for the remaining to maximize the score.

The Two-Pointer approach leverages two pointers to parse through the string and eliminate substrings optimally. By managing two scanning points, determining which pattern to remove can be executed with minimal operations, optimizing score calculation effectively.

This C solution uses two pointers combined with a simulated stack to efficiently parse and optimize substring removal by maximizing the scores at each step through linear traversal.

We can assume that the score of substring "ab" is always no less than the score of substring "ba". If not, we can swap "a" and "b", and simultaneously swap x and y.

Next, we only need to consider the case where the string contains only "a" and "b". If the string contains other characters, we can treat them as split points, dividing the string into several substrings that contain only "a" and "b", and then calculate the score for each substring separately.

We observe that for a substring containing only "a" and "b", no matter what operations we take, we will eventually be left with only one type of character, or an empty string. Since each operation removes one "a" and one "b" simultaneously, the total number of operations is fixed. We can greedily remove "ab" first, then remove "ba", which ensures the maximum score.

Therefore, we can use two variables cnt1 and cnt2 to record the counts of "a" and "b" respectively, then traverse the string and update cnt1 and cnt2 according to different cases of the current character, while calculating the score.

For the current character c being traversed:

• If c is "a", since we want to remove "ab" first, we don't eliminate this character at this time, only increment cnt1;
• If c is "b", if cnt1 > 0 at this time, we can eliminate one "ab" and add x points; otherwise, we can only increment cnt2;
• If c is another character, then for this substring, we have cnt2 "b"s and cnt1 "a"s left. We can eliminate min(cnt1, cnt2) "ba"s and add several y points.

After traversal, we need to handle the remaining "ba"s and add several y points.

The time complexity is O(n), where n is the length of string s. The space complexity is O(1).