maximum_score_from_removing_substrings

View Source

 1# @leet start
 2class Solution:
 3    def maximumGain(self, s: str, x: int, y: int) -> int:
 4        """
 5        This question gives us a string, `s`, and two numbers, `x` and `y`,
 6        which are the points gained from removing `ab` and `ba` from the string
 7        respectively.
 8
 9        We want to maximize the score from removing all the substrings.
10
11        We can test every removal by DFSing in $O(2^n)$ time.
12        We can test every removal in $O(n^2)$ time with caching, as a DP problem.
13        The optimal solution can be done in $O(n)$ time.
14
15        We can do this by first checking which string, `ab` or `ba` is more
16        valued. We always want to remove the more valued one first, because
17        that maximizes our score.
18
19        Imagine a string `baba`, where `ab` is worth 1 and `ba` is worth 2.
20        If we take `ab` first, then `ba`, we get 3 points.
21        However, if we take `ba` twice, we get 4 points.
22        Thus, we want to take as many `ba`s first, then take any remaining
23        `ab`s. In the case they're equally valued, it doesn't matter which one
24        we take.
25        """
26        order = [("a", "b", x), ("b", "a", y)]
27        if x < y:
28            order.reverse()
29
30        res = 0
31        for l, r, points in order:
32            stack = []
33            for c in s:
34                if stack and stack[-1] == l and c == r:
35                    stack.pop()
36                    res += points
37                else:
38                    stack.append(c)
39            s = stack
40        return res
41
42
43# @leet end
44
45
46def test():
47    assert 2 + 2 == 4

class Solution: View Source

 3class Solution:
 4    def maximumGain(self, s: str, x: int, y: int) -> int:
 5        """
 6        This question gives us a string, `s`, and two numbers, `x` and `y`,
 7        which are the points gained from removing `ab` and `ba` from the string
 8        respectively.
 9
10        We want to maximize the score from removing all the substrings.
11
12        We can test every removal by DFSing in $O(2^n)$ time.
13        We can test every removal in $O(n^2)$ time with caching, as a DP problem.
14        The optimal solution can be done in $O(n)$ time.
15
16        We can do this by first checking which string, `ab` or `ba` is more
17        valued. We always want to remove the more valued one first, because
18        that maximizes our score.
19
20        Imagine a string `baba`, where `ab` is worth 1 and `ba` is worth 2.
21        If we take `ab` first, then `ba`, we get 3 points.
22        However, if we take `ba` twice, we get 4 points.
23        Thus, we want to take as many `ba`s first, then take any remaining
24        `ab`s. In the case they're equally valued, it doesn't matter which one
25        we take.
26        """
27        order = [("a", "b", x), ("b", "a", y)]
28        if x < y:
29            order.reverse()
30
31        res = 0
32        for l, r, points in order:
33            stack = []
34            for c in s:
35                if stack and stack[-1] == l and c == r:
36                    stack.pop()
37                    res += points
38                else:
39                    stack.append(c)
40            s = stack
41        return res

def maximumGain(self, s: str, x: int, y: int) -> int: View Source

 4    def maximumGain(self, s: str, x: int, y: int) -> int:
 5        """
 6        This question gives us a string, `s`, and two numbers, `x` and `y`,
 7        which are the points gained from removing `ab` and `ba` from the string
 8        respectively.
 9
10        We want to maximize the score from removing all the substrings.
11
12        We can test every removal by DFSing in $O(2^n)$ time.
13        We can test every removal in $O(n^2)$ time with caching, as a DP problem.
14        The optimal solution can be done in $O(n)$ time.
15
16        We can do this by first checking which string, `ab` or `ba` is more
17        valued. We always want to remove the more valued one first, because
18        that maximizes our score.
19
20        Imagine a string `baba`, where `ab` is worth 1 and `ba` is worth 2.
21        If we take `ab` first, then `ba`, we get 3 points.
22        However, if we take `ba` twice, we get 4 points.
23        Thus, we want to take as many `ba`s first, then take any remaining
24        `ab`s. In the case they're equally valued, it doesn't matter which one
25        we take.
26        """
27        order = [("a", "b", x), ("b", "a", y)]
28        if x < y:
29            order.reverse()
30
31        res = 0
32        for l, r, points in order:
33            stack = []
34            for c in s:
35                if stack and stack[-1] == l and c == r:
36                    stack.pop()
37                    res += points
38                else:
39                    stack.append(c)
40            s = stack
41        return res

This question gives us a string, s, and two numbers, x and y, which are the points gained from removing ab and ba from the string respectively.

We want to maximize the score from removing all the substrings.

We can test every removal by DFSing in $O(2^n)$ time. We can test every removal in $O(n^2)$ time with caching, as a DP problem. The optimal solution can be done in $O(n)$ time.

We can do this by first checking which string, ab or ba is more valued. We always want to remove the more valued one first, because that maximizes our score.

Imagine a string baba, where ab is worth 1 and ba is worth 2. If we take ab first, then ba, we get 3 points. However, if we take ba twice, we get 4 points. Thus, we want to take as many bas first, then take any remaining abs. In the case they're equally valued, it doesn't matter which one we take.

def test(): View Source

47def test():
48    assert 2 + 2 == 4