1717. Maximum Score From Removing Substrings - Solution

The problem

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.
- For example, when removing "ab" from "cabxbae" it becomes "cxbae".
Remove substring "ba" and gain y points.
- For example, when removing "ba" from "cabxbae" it becomes "cabxe".

Return the maximum points you can gain after applying the above operations on s.

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 <= 10⁵
1 <= x, y <= 10⁴
s consists of lowercase English letters.

Approach overview

Problem Overview: You are given a string s and two scores x and y. Removing substring "ab" earns x points and removing "ba" earns y points. After each removal the string closes the gap, potentially creating new substrings. The goal is to maximize the total score.

Approach 1: Greedy Approach with Stack (O(n) time, O(n) space)

The key observation: always remove the higher scoring substring first. If x > y, remove "ab" first; otherwise remove "ba". Scan the string and simulate removals using a stack. When the current character forms the target pair with the stack top, pop the stack and add the corresponding score. Otherwise push the character. After the first pass, run the same process on the remaining characters to remove the other substring type. This greedy ordering ensures higher-value removals happen before they get blocked by lower-value ones. Time complexity is O(n) because each character is pushed and popped at most once. Space complexity is O(n) for the stack.

This method relies on greedy decision making and local pair elimination. It appears frequently in stack and greedy interview problems where removing patterns affects future structure.

Approach 2: Two-Pointer Counting Strategy (O(n) time, O(1) space)

You can simulate the same greedy logic without an explicit stack by counting characters while scanning. Process the higher-value substring first. Maintain counters for the first and second characters in the pair. When a matching pair forms, increment the score and decrement the counter instead of storing characters. Characters that cannot form the preferred pair are carried forward and used when processing the second substring type. This approach mimics stack behavior using counters and avoids storing the entire intermediate string.

The scan still touches each character a constant number of times, giving O(n) time complexity with O(1) extra space. This is a good choice when memory constraints matter or when implementing in performance-sensitive environments.

The problem primarily tests understanding of greedy ordering in string manipulation. Removing the wrong pair first can destroy opportunities for higher scoring pairs later.

Recommended for interviews: The greedy stack approach is the most expected solution. It clearly demonstrates why removing the higher-value substring first maximizes the score and is easy to reason about during discussion. The two-pointer version is a space-optimized refinement that strong candidates may mention after presenting the stack-based solution.

Approach 1: Greedy Approach with Stack

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.

Python

def max_score(s, x, y):
    score = 0
    stack = []
    first, second = ('a', 'b') if x > y else ('b', 'a')
    first_points, second_points = (x, y) if x > y else (y, x)
    
    # Remove the higher score patterns first
    for char in s:
        if stack and stack[-1] == first and char == second:
            stack.pop()
            score += first_points
        else:
            stack.append(char)
    
    # Second pass to remove remaining patterns
    second_pass = []
    while stack:
        char = stack.pop()
        if second_pass and second_pass[-1] == second and char == first:
            second_pass.pop()
            score += second_points
        else:
            second_pass.append(char)

    return score

s = "cdbcbbaaabab"
x = 4
y = 5
print(max_score(s, x, y))

Java

import java.util.Stack;

public class MaxScore {
    public static int maxScore(String s, int x, int y) {
        int score = 0;
        Stack<Character> stack = new Stack<>();
        char first = x > y ? 'a' : 'b';
        char second = x > y ? 'b' : 'a';
        int firstPoints = x > y ? x : y;
        int secondPoints = x > y ? y : x;

        // Remove the higher score patterns first
        for (char c : s.toCharArray()) {
            if (!stack.isEmpty() && stack.peek() == first && c == second) {
                stack.pop();
                score += firstPoints;
            } else {
                stack.push(c);
            }
        }

        // Second pass to remove remaining patterns
        Stack<Character> secondStack = new Stack<>();
        while (!stack.isEmpty()) {
            char c = stack.pop();
            if (!secondStack.isEmpty() && secondStack.peek() == second && c == first) {
                secondStack.pop();
                score += secondPoints;
            } else {
                secondStack.push(c);
            }
        }

        return score;
    }

    public static void main(String[] args) {
        String s = "cdbcbbaaabab";
        int x = 4;
        int y = 5;
        System.out.println(maxScore(s, x, y));
    }
}

C++

#include <iostream>
#include <string>
#include <stack>

int maxScore(std::string s, int x, int y) {
    int score = 0;
    std::stack<char> stk;
    char first = x > y ? 'a' : 'b';
    char second = x > y ? 'b' : 'a';
    int firstPoints = x > y ? x : y;
    int secondPoints = x > y ? y : x;
    
    // Remove higher score patterns first
    for (char c : s) {
        if (!stk.empty() && stk.top() == first && c == second) {
            stk.pop();
            score += firstPoints;
        } else {
            stk.push(c);
        }
    }
    
    // Second pass to remove remaining lower score patterns
    std::string remaining;
    while (!stk.empty()) {
        remaining += stk.top();
        stk.pop();
    }
    std::reverse(remaining.begin(), remaining.end());

    for (char c : remaining) {
        if (!stk.empty() && stk.top() == second && c == first) {
            stk.pop();
            score += secondPoints;
        } else {
            stk.push(c);
        }
    }
    
    return score;
}

int main() {
    std::string s = "cdbcbbaaabab";
    int x = 4;
    int y = 5;
    std::cout << maxScore(s, x, y) << std::endl;
    return 0;
}

JavaScript

function maxScore(s, x, y) {
    let score = 0;
    let stack = [];
    let first = x > y ? 'a' : 'b';
    let second = x > y ? 'b' : 'a';
    let firstPoints = x > y ? x : y;
    let secondPoints = x > y ? y : x;

    // Remove higher score patterns first
    for (let char of s) {
        if (stack.length > 0 && stack[stack.length - 1] === first && char === second) {
            stack.pop();
            score += firstPoints;
        } else {
            stack.push(char);
        }
    }

    // Second pass to remove remaining patterns
    let secondPass = [];
    while (stack.length > 0) {
        let char = stack.pop();
        if (secondPass.length > 0 && secondPass[secondPass.length - 1] === second && char === first) {
            secondPass.pop();
            score += secondPoints;
        } else {
            secondPass.push(char);
        }
    }

    return score;
}

let s = "cdbcbbaaabab";
let x = 4;
let y = 5;
console.log(maxScore(s, x, y));

#include <stdio.h>
#include <string.h>

int maxScore(char* s, int x, int y) {
    int score = 0;
    char stack[strlen(s)];
    int top = -1;
    char first = x > y ? 'a' : 'b';
    char second = x > y ? 'b' : 'a';
    int firstPoints = x > y ? x : y;
    int secondPoints = x > y ? y : x;
    
    // Remove the higher score patterns first
    for (int i = 0; s[i] != '\0'; i++) {
        if (top >= 0 && stack[top] == first && s[i] == second) {
            top--; // pop from stack
            score += firstPoints;
        } else {
            stack[++top] = s[i]; // push onto stack
        }
    }
    
    // Second pass to remove remaining patterns
    int newTop = -1;
    for (int i = 0; i <= top; i++) {
        if (newTop >= 0 && stack[newTop] == second && stack[i] == first) {
            newTop--; // pop
            score += secondPoints;
        } else {
            stack[++newTop] = stack[i]; // push
        }
    }
    
    return score;
}

int main() {
    char s[] = "cdbcbbaaabab";
    int x = 4;
    int y = 5;
    printf("%d\n", maxScore(s, x, y));
    return 0;
}

using System;
using System.Collections.Generic;

public class MaxScore {
    public static int MaxScoreFunc(string s, int x, int y) {
        int score = 0;
        Stack<char> stack = new Stack<char>();
        char first = x > y ? 'a' : 'b';
        char second = x > y ? 'b' : 'a';
        int firstPoints = x > y ? x : y;
        int secondPoints = x > y ? y : x;

        // Remove the higher score patterns first
        foreach (char c in s) {
            if (stack.Count > 0 && stack.Peek() == first && c == second) {
                stack.Pop();
                score += firstPoints;
            } else {
                stack.Push(c);
            }
        }

        // Second pass to remove remaining patterns
        Stack<char> secondStack = new Stack<char>();
        while (stack.Count > 0) {
            char c = stack.Pop();
            if (secondStack.Count > 0 && secondStack.Peek() == second && c == first) {
                secondStack.Pop();
                score += secondPoints;
            } else {
                secondStack.Push(c);
            }
        }

        return score;
    }

    public static void Main(string[] args) {
        string s = "cdbcbbaaabab";
        int x = 4;
        int y = 5;
        Console.WriteLine(MaxScoreFunc(s, x, y));
    }
}

The Python solution uses a list to simulate a stack, performing two sweeps across the input string to prioritize maximum scoring substring removal. It is efficient and concise, taking advantage of Python's list behaviors.

Complexity

Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(n), owing to the usage of lists as stacks.

Try this approach in the editor

Approach 2: Two-Pointer Approach

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.

Python

def max_score(s, x, y):
    score = 0
    stack = []

    first, second = ('a', 'b') if x > y else ('b', 'a')
    first_points, second_points = (x, y) if x > y else (y, x)

    for char in s:
        if stack and stack[-1] == first and char == second:
            stack.pop()
            score += first_points
        else:
            stack.append(char)

    s = stack
    stack = []

    for char in s:
        if stack and stack[-1] == second and char == first:
            stack.pop()
            score += second_points
        else:
            stack.append(char)

    return score

s = "cdbcbbaaabab"
x = 4
y = 5
print(max_score(s, x, y))

Java

public class MaxScore {
    public static int maxScore(String s, int x, int y) {
        int score = 0;
        StringBuilder stack = new StringBuilder();

        char first = x > y ? 'a' : 'b';
        char second = x > y ? 'b' : 'a';
        int firstPoints = x > y ? x : y;
        int secondPoints = x > y ? y : x;

        for (int i = 0; i < s.length(); i++) {
            if (stack.length() > 0 && stack.charAt(stack.length() - 1) == first && s.charAt(i) == second) {
                stack.deleteCharAt(stack.length() - 1);
                score += firstPoints;
            } else {
                stack.append(s.charAt(i));
            }
        }

        s = stack.toString();
        stack = new StringBuilder();

        for (int i = 0; i < s.length(); i++) {
            if (stack.length() > 0 && stack.charAt(stack.length() - 1) == second && s.charAt(i) == first) {
                stack.deleteCharAt(stack.length() - 1);
                score += secondPoints;
            } else {
                stack.append(s.charAt(i));
            }
        }

        return score;
    }

    public static void main(String[] args) {
        String s = "cdbcbbaaabab";
        int x = 4;
        int y = 5;
        System.out.println(maxScore(s, x, y));
    }
}

C++

#include <iostream>
#include <string>

int maxScore(std::string s, int x, int y) {
    int score = 0;
    int left = 0;
    int right = 0;
    std::string stack = "";

    char first = x > y ? 'a' : 'b';
    char second = x > y ? 'b' : 'a';
    int firstPoints = x > y ? x : y;
    int secondPoints = x > y ? y : x;

    while (right < s.length()) {
        if (!stack.empty() && stack.back() == first && s[right] == second) {
            stack.pop_back();
            score += firstPoints;
        } else {
            stack.push_back(s[right]);
        }
        right++;
    }

    s = stack;
    stack.clear();
    right = 0;

    while (right < s.length()) {
        if (!stack.empty() && stack.back() == second && s[right] == first) {
            stack.pop_back();
            score += secondPoints;
        } else {
            stack.push_back(s[right]);
        }
        right++;
    }

    return score;
}

int main() {
    std::string s = "cdbcbbaaabab";
    int x = 4;
    int y = 5;
    std::cout << maxScore(s, x, y) << std::endl;
    return 0;
}

JavaScript

function maxScore(s, x, y) {
    let score = 0;
    let stack = [];

    const [first, second] = x > y ? ['a', 'b'] : ['b', 'a'];
    const [firstPoints, secondPoints] = x > y ? [x, y] : [y, x];

    for (let char of s) {
        if (stack.length > 0 && stack[stack.length - 1] === first && char === second) {
            stack.pop();
            score += firstPoints;
        } else {
            stack.push(char);
        }
    }

    const newS = stack;
    stack = [];

    for (let char of newS) {
        if (stack.length > 0 && stack[stack.length - 1] === second && char === first) {
            stack.pop();
            score += secondPoints;
        } else {
            stack.push(char);
        }
    }

    return score;
}

let s = "cdbcbbaaabab";
let x = 4;
let y = 5;
console.log(maxScore(s, x, y));

#include <stdio.h>
#include <string.h>

int maxScore(char* s, int x, int y) {
    int score = 0;
    int n = strlen(s);
    int left = 0;
    int right = 0;
    int stackTop = 0;
    char stack[n];

    // Decide the order based on point values
    char first = x > y ? 'a' : 'b';
    char second = x > y ? 'b' : 'a';
    int firstPoints = x > y ? x : y;
    int secondPoints = x > y ? y : x;

    // First scan pointers
    while (right < n) {
        if (stackTop > 0 && stack[stackTop - 1] == first && s[right] == second) {
            stackTop--;
            score += firstPoints;
        } else {
            stack[stackTop++] = s[right];
        }
        right++;
    }

    // Second sweep for remaining patterns
    right = stackTop;
    stackTop = 0;
    while (left < right) {
        if (stackTop > 0 && stack[stackTop - 1] == second && s[left] == first) {
            stackTop--;
            score += secondPoints;
        } else {
            stack[stackTop++] = s[left];
        }
        left++;
    }

    return score;
}

int main() {
    char s[] = "cdbcbbaaabab";
    int x = 4;
    int y = 5;
    printf("%d\n", maxScore(s, x, y));
    return 0;
}

using System;
using System.Text;
using System.Collections.Generic;

public class MaxScore {
    public static int MaxScoreFunc(string s, int x, int y) {
        int score = 0;
        StringBuilder stack = new StringBuilder();

        char first = x > y ? 'a' : 'b';
        char second = x > y ? 'b' : 'a';
        int firstPoints = x > y ? x : y;
        int secondPoints = x > y ? y : x;

        foreach (char c in s) {
            if (stack.Length > 0 && stack[stack.Length - 1] == first && c == second) {
                stack.Length--;
                score += firstPoints;
            } else {
                stack.Append(c);
            }
        }

        s = stack.ToString();
        stack = new StringBuilder();

        foreach (char c in s) {
            if (stack.Length > 0 && stack[stack.Length - 1] == second && c == first) {
                stack.Length--;
                score += secondPoints;
            } else {
                stack.Append(c);
            }
        }

        return score;
    }

    public static void Main(string[] args) {
        string s = "cdbcbbaaabab";
        int x = 4;
        int y = 5;
        Console.WriteLine(MaxScoreFunc(s, x, y));
    }
}

This Python approach utilizes lists for stacking operations, maintaining quick management of substrings within two parsing sequences, offering a neat method to maximize points efficiently through strict but minimal operations.

Complexity

Time Complexity: O(n), n being the string length.
Space Complexity: O(n), accounts for stack operations on the input string.

Try this approach in the editor

Approach 3: Greedy

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).

TypeScript

function maximumGain(s: string, x: number, y: number): number {
    let [a, b] = ['a', 'b'];
    if (x < y) {
        [x, y] = [y, x];
        [a, b] = [b, a];
    }

    let [ans, cnt1, cnt2] = [0, 0, 0];
    for (let c of s) {
        if (c === a) {
            cnt1++;
        } else if (c === b) {
            if (cnt1) {
                ans += x;
                cnt1--;
            } else {
                cnt2++;
            }
        } else {
            ans += Math.min(cnt1, cnt2) * y;
            cnt1 = 0;
            cnt2 = 0;
        }
    }
    ans += Math.min(cnt1, cnt2) * y;
    return ans;
}

func maximumGain(s string, x int, y int) (ans int) {
	a, b := 'a', 'b'
	if x < y {
		x, y = y, x
		a, b = b, a
	}

	var cnt1, cnt2 int
	for _, c := range s {
		if c == a {
			cnt1++
		} else if c == b {
			if cnt1 > 0 {
				ans += x
				cnt1--
			} else {
				cnt2++
			}
		} else {
			ans += min(cnt1, cnt2) * y
			cnt1, cnt2 = 0, 0
		}
	}
	ans += min(cnt1, cnt2) * y
	return
}

Rust

impl Solution {
    pub fn maximum_gain(s: String, mut x: i32, mut y: i32) -> i32 {
        let (mut a, mut b) = ('a', 'b');
        if x < y {
            std::mem::swap(&mut x, &mut y);
            std::mem::swap(&mut a, &mut b);
        }

        let mut ans = 0;
        let mut cnt1 = 0;
        let mut cnt2 = 0;

        for c in s.chars() {
            if c == a {
                cnt1 += 1;
            } else if c == b {
                if cnt1 > 0 {
                    ans += x;
                    cnt1 -= 1;
                } else {
                    cnt2 += 1;
                }
            } else {
                ans += cnt1.min(cnt2) * y;
                cnt1 = 0;
                cnt2 = 0;
            }
        }

        ans += cnt1.min(cnt2) * y;
        ans
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Greedy Approach with Stack	Time Complexity: O(n), where n is the length of the string. Space Complexity: O(n), owing to the usage of lists as stacks.
Two-Pointer Approach	Time Complexity: O(n), n being the string length. Space Complexity: O(n), accounts for stack operations on the input string.
Greedy	–

Complexity analysis

Approach	Time	Space	When to Use
Greedy with Stack	O(n)	O(n)	Best general solution. Easy to implement and explain during interviews.
Two-Pointer Counting	O(n)	O(1)	When minimizing memory usage or avoiding auxiliary stack storage.

Frequently asked questions

Is Maximum Score From Removing Substrings easy or hard?

Maximum Score From Removing Substrings is rated Medium difficulty on LeetCode. The implementation is straightforward once the greedy insight is recognized, but identifying that the higher scoring substring must be removed first is the key challenge.

Maximum Score From Removing Substrings Python/Java solution

Implement the greedy strategy: remove the higher-value substring first using a stack or counters, then process the remaining string for the other pair. The same logic works across Python, Java, C++, JavaScript, and C# with linear time complexity.

How to solve Maximum Score From Removing Substrings in O(n)?

Use a greedy strategy. Determine which substring ('ab' or 'ba') gives higher points and remove it first while scanning the string using a stack or counters. After finishing the first pass, process the remaining characters to remove the other substring type. This guarantees maximum score in linear time.

What is the best approach for Maximum Score From Removing Substrings?

The greedy approach with a stack is the most common solution. Always remove the higher scoring substring first ('ab' or 'ba'), then process the remaining string for the other pair. Each character is processed once, giving O(n) time complexity and O(n) space for the stack.

Is Maximum Score From Removing Substrings asked at Google/Amazon/Meta?

Greedy string manipulation and stack-based pattern removal problems frequently appear in interviews at companies like Amazon, Google, and Meta. This problem tests understanding of greedy ordering and efficient string processing in O(n) time.

What data structure is used in Maximum Score From Removing Substrings?

The most common solution uses a stack to track characters while scanning the string. The stack helps detect when the current character forms a removable pair with the previous one. An optimized approach can replace the stack with simple counters and two-pointer style scanning.

What is the time complexity of Maximum Score From Removing Substrings?

The optimal solution runs in O(n) time where n is the length of the string. Each character is pushed and popped from the stack at most once or processed once in the two-pointer version. Space complexity is O(n) with a stack or O(1) using the counting approach.

Maximum Score From Removing Substrings solution and explanation

The problem

Approach overview

Approach 1: Greedy Approach with Stack

Approach 2: Two-Pointer Approach

Approach 3: Greedy

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Maximum Score From Removing Substrings solution and explanation

The problem

Approach overview

Approach 1: Greedy Approach with Stack

Approach 2: Two-Pointer Approach

Approach 3: Greedy

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems