Skip to content

Latest commit

 

History

History
376 lines (309 loc) · 9.92 KB

README_EN.md

File metadata and controls

376 lines (309 loc) · 9.92 KB
comments difficulty edit_url rating source tags
true
Medium
1867
Biweekly Contest 43 Q2
Stack
Greedy
String

1717. Maximum Score From Removing Substrings

中文文档

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. 
    <ul>
	<li>For example, when removing <code>&quot;ab&quot;</code> from <code>&quot;c<u>ab</u>xbae&quot;</code> it becomes <code>&quot;cxbae&quot;</code>.</li>
</ul>
</li>
<li>Remove substring <code>&quot;ba&quot;</code> and gain <code>y</code> points.
<ul>
	<li>For example, when removing <code>&quot;ba&quot;</code> from <code>&quot;cabx<u>ba</u>e&quot;</code> it becomes <code>&quot;cabxe&quot;</code>.</li>
</ul>
</li>

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 <= 105
  • 1 <= x, y <= 104
  • s consists of lowercase English letters.

Solutions

Solution 1: Greedy

Let's assume that the score of the substring "ab" is always not lower than the score of the 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 a dividing point, splitting 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 are taken, in the end, there will only be one type of character left, or an empty string. Since each operation will delete one "a" and one "b" simultaneously, the total number of operations is fixed. We can greedily delete "ab" first, then "ba", to ensure the maximum score.

Therefore, we can use two variables $\textit{cnt1}$ and $\textit{cnt2}$ to record the number of "a" and "b", respectively. Then, we traverse the string, update $\textit{cnt1}$ and $\textit{cnt2}$ based on the current character, and calculate the score.

For the current character $c$:

  • If $c$ is "a", since we need to delete "ab" first, we do not eliminate this character at this time, only increase $\textit{cnt1}$;
  • If $c$ is "b", if $\textit{cnt1} &gt; 0$ at this time, we can eliminate an "ab" and add $x$ points; otherwise, we can only increase $\textit{cnt2}$;
  • If $c$ is another character, then for this substring, we are left with $\textit{cnt2}$ "b" and $\textit{cnt1}$ "a", we can eliminate $\min(\textit{cnt1}, \textit{cnt2})$ "ab" and add $y$ points.

After the traversal is finished, we also need to additionally handle the remaining "ab", adding several $y$ points.

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

Python3

class Solution:
    def maximumGain(self, s: str, x: int, y: int) -> int:
        a, b = "a", "b"
        if x < y:
            x, y = y, x
            a, b = b, a
        ans = cnt1 = cnt2 = 0
        for c in s:
            if c == a:
                cnt1 += 1
            elif c == b:
                if cnt1:
                    ans += x
                    cnt1 -= 1
                else:
                    cnt2 += 1
            else:
                ans += min(cnt1, cnt2) * y
                cnt1 = cnt2 = 0
        ans += min(cnt1, cnt2) * y
        return ans

Java

class Solution {
    public int maximumGain(String s, int x, int y) {
        char a = 'a', b = 'b';
        if (x < y) {
            int t = x;
            x = y;
            y = t;
            char c = a;
            a = b;
            b = c;
        }
        int ans = 0, cnt1 = 0, cnt2 = 0;
        int n = s.length();
        for (int i = 0; i < n; ++i) {
            char c = s.charAt(i);
            if (c == a) {
                cnt1++;
            } else if (c == b) {
                if (cnt1 > 0) {
                    ans += x;
                    cnt1--;
                } else {
                    cnt2++;
                }
            } else {
                ans += Math.min(cnt1, cnt2) * y;
                cnt1 = 0;
                cnt2 = 0;
            }
        }
        ans += Math.min(cnt1, cnt2) * y;
        return ans;
    }
}

C++

class Solution {
public:
    int maximumGain(string s, int x, int y) {
        char a = 'a', b = 'b';
        if (x < y) {
            swap(x, y);
            swap(a, b);
        }

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

Go

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
}

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;
}

JavaScript

function maximumGain(s, x, y) {
    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;
}

Solution 2: Greedy + Stack

TypeScript

function maximumGain(s: string, x: number, y: number): number {
    const stk: string[] = [];
    const pairs: Record<string, string> = { a: 'b', b: 'a' };
    const pair = x > y ? ['a', 'b'] : ['b', 'a'];
    let str = [...s];
    let ans = 0;
    let havePairs = true;

    while (havePairs) {
        for (const p of pair) {
            havePairs = true;

            for (const ch of str) {
                if (stk.at(-1) === p && ch === pairs[p]) {
                    stk.pop();
                } else stk.push(ch);
            }

            if (str.length === stk.length) havePairs = false;

            const multiplier = p === 'a' ? x : y;
            ans += (multiplier * (str.length - stk.length)) / 2;
            str = [...stk];
            stk.length = 0;
        }
    }

    return ans;
}

JavaeScript

function maximumGain(s, x, y) {
    const stk = [];
    const pairs = { a: 'b', b: 'a' };
    const pair = x > y ? ['a', 'b'] : ['b', 'a'];
    let str = [...s];
    let ans = 0;
    let havePairs = true;

    while (havePairs) {
        for (const p of pair) {
            havePairs = true;

            for (const ch of str) {
                if (stk.at(-1) === p && ch === pairs[p]) {
                    stk.pop();
                } else stk.push(ch);
            }

            if (str.length === stk.length) havePairs = false;

            const multiplier = p === 'a' ? x : y;
            ans += (multiplier * (str.length - stk.length)) / 2;
            str = [...stk];
            stk.length = 0;
        }
    }

    return ans;
}