LeetCode 🟡 1717. Maximum Score From Removing Substrings

🔗 🟡 1717. Maximum Score From Removing Substrings 1868

tags: Biweekly Contest 43 字串(String) 貪心(Greedy) 堆疊(Stack)

題意

給定一個字串 $s$ 和兩個整數 $x$ 和 $y$。你可以執行以下兩種操作任意次數：

1. 移除子字串 “ab” 並獲得 $x$ 分。
   • 例如，從 “cabxbae” 移除 “ab” 後變成 “cxbae”。
2. 移除子字串 “ba” 並獲得 $y$ 分。
   • 例如，從 “cabxbae” 移除 “ba” 後變成 “cabxe”。

請返回在對 $s$ 進行上述操作後所能獲得的最高分數。

思路：分組循環 + 貪心(Greedy)

首先可以假設 $x \geq y$，如果不是，則將字串 $s$ 中的 ‘a’ 和 ‘b’ 互換，並交換 $x$ 和 $y$ 的值。這樣可以保證移除 “ab” 的得分高於 “ba”。

根據題意，我們只需要處理 ‘a’ 和 ‘b’ 這兩種字元，因此可以使用 分組循環 的技巧來處理字串，使得每組內的字元都是 ‘a’ 或 ‘b’。

接著可以基於 貪心(Greedy) 的思路，優先移除該組內的 “ab”，然後再移除剩餘的 “ba”。這樣可以保證獲得最高分數。

貪心思路的正確性證明如下：

• 當我們先移除了所有 “ab” 時，等同移除了右邊有 ‘b’ 的所有 ‘a’。
• 假設在先移除 “ab” 後，仍可得到更高的分數。即在移除了某個 “ba” 後，可以得到 “ab”。即 $"abab" \Rightarrow "ab" \Rightarrow ""$。
• 但上述情況中的 “abab” 會與已經移除了所有 “ab” 的情況產生 矛盾 ，故不可能存在這樣的情況。

方法一：堆疊(Stack)

在分組循環時，可以使用兩個 堆疊(Stack) $st1$ 和 $st2$ 來模擬貪心的過程。首先需要注意，由於我們只需要考慮 ‘a’ 和 ‘b’，因此在分組循環時我們處理的子字串只包含這兩種字元。

具體步驟如下：

• 首先正向遍歷組內的字元，使用 $st1$ 來消除 “ab”。
  • 如果遇到 ‘a’，則將其推入堆疊。
  • 如果遇到 ‘b’，則檢查堆疊頂部是否為 ‘a’，如果是，則代表可以消除 “ab”，並增加得分 $x$；否則，將 ‘b’ 推入 $st1$。
• 當 $st1$ 中無法再匹配 “ab” 時，初始化另一個用來消除 “ba” 的堆疊 $st2$，並將剩餘的字符從 $st1$ 移動到 $st2$ 中進行匹配和移除 “ba”。
  • 如果 $st1$ 頂部是 ‘a’，則將其推入 $st2$；
  • 如果 $st1$ 頂部是 ‘b’ ，則檢查 $st2$ 頂部是否為 ‘a’，如果是，則代表可以消除 “ba”，並增加得分 $y$；否則，將 ‘b’ 推入 $st2$。

但在消除完所有 “ab” 後，剩下的字串必然是 “b…b…a…a” 的形式，因此在消除 “ba” 時，若遇到 “b” 且已經沒有 “a” 可以消除，則可以提前結束循環。

複雜度分析

• 時間複雜度：$O(n)$，其中 $n$ 是字串的長度。
  • 我們只需要遍歷字串一次，每個字符最多被處理兩次（一次在 $st1$，一次在 $st2$）。
• 空間複雜度：$O(n)$，在最壞情況下，堆疊可能需要存儲整個字串。

PythonC++

class Solution:
    def maximumGain(self, s: str, x: int, y: int) -> int:
        n = len(s)
        if x < y: # 保證 x > y ，否則將 s 中的 a 和 b 互換，並交換 x 和 y 的值
            lst = list(s)
            for i, ch in enumerate(lst):
                if ch == 'a': lst[i] = 'b'
                elif ch == 'b': lst[i] = 'a'
            x, y = y, x
            s = ''.join(lst)
        ans = 0
        i = 0
        while (i < n): # 分組循環
            while i < n and s[i] != 'a' and s[i] != 'b': # 跳過非 a 和 b 的字元
                i += 1
            st1 = [] # 用來消除 "ab"
            while i < n and (s[i] == 'a' or s[i] == 'b'):
                if s[i] == 'a':
                    st1.append('a')
                else:
                    if st1 and st1[-1] == 'a':
                        ans += x
                        st1.pop()
                    else:
                        st1.append('b')
                i += 1 
            st2 = [] # 用來消除 "ba"
            while st1:
                if st1[-1] == 'a':
                    st2.append(st1.pop())
                else:
                    if st2 and st2[-1] == 'a':
                        ans += y
                        st1.pop()
                        st2.pop()
                    else: # 這裡可以提前 break
                        # break
                        st2.append(st1.pop())
        return ans

class Solution {
public:
    int maximumGain(string s, int x, int y) {
        int n = s.size();
        if (x < y) {
            for (int i = 0; i < n; i++) {
                if (s[i] == 'a') s[i] = 'b';
                else if (s[i] == 'b') s[i] = 'a';
            }
            swap(x, y);
        }
        int i = 0, ans = 0;
        while (i < n) {
            while (i < n && s[i] != 'a' && s[i] != 'b') i++;
            stack<char> st1;
            while (i < n && (s[i] == 'a' || s[i] == 'b')) {
                if (s[i] == 'a') st1.push('a');
                else {
                    if (!st1.empty() && st1.top() == 'a') {
                        ans += x;
                        st1.pop();
                    } else {
                        st1.push('b');
                    }
                }
                i++;
            }
            stack<char> st2;
            while (!st1.empty()) {
                if (st1.top() == 'a') {
                    st2.push(st1.top());
                    st1.pop();
                } else {
                    if (!st2.empty() && st2.top() == 'a') {
                        ans += y;
                        st1.pop();
                        st2.pop();
                    } else {
                        st2.push(st1.top());
                        st1.pop();
                    }
                }
            }
        }
        return ans;
    }
};

方法二：維護 $a$ 和 $b$ 的數量

在證明貪心思路的正確性時，我們提到了在消除完 “ab” 後，剩下的字串必然是 “b…b…a…a” 的形式。因此，我們可以維護 $a$ 和 $b$ 的數量，並根據 $a$ 和 $b$ 的數量來計算得分，說明如下：

• 在方法一消除 “ab” 的過程中，只有在遇到 $b$ 時才能有消除 “ab” 的機會，若此時堆疊的頂端是 “a”，則可以消除 “ab” 。
• 而在這個過程中，剩餘的所有 “a” 都必然會在堆疊的頂端，因此我們實際上只需要維護 $a$ 的數量。
• 而在消除 “ba” 的過程中，由於剩餘的字串是 “b…b…a…a” 的形式，因此剩餘 “a” 的數量和剩餘 “b” 的數量兩者的最小值即為可以消除的 “ba” 的數量。

具體步驟如下：

1. 初始化 $cnt_a$ 和 $cnt_b$ 的數量為 $0$。
2. 對於組內的所有字元 $s[i]$：
   • 如果 $s[i] == \text{'a'}$，則 $cnt_a$ 加一。
   • 如果 $s[i] == \text{'b'}$：
     • 如果 $cnt_a > 0$，則消除 “ab”，並增加得分 $x$，$cnt_a$ 減一。
     • 否則，$cnt_b$ 加一，代表消除完所有 “ab” 後剩餘的 “b” 數量。
3. 最後，增加 $min(cnt_a, cnt_b) \times y$ 到得分中，代表透過消除 “ba” 可以獲得的分數。

複雜度分析

• 時間複雜度：$O(n)$，其中 $n$ 是字串的長度。我們只需要遍歷字串一次。
• 空間複雜度：$O(1)$。

PythonC++

class Solution:
    def maximumGain(self, s: str, x: int, y: int) -> int:
        n = len(s)
        if x < y:
            lst = list(s)
            for i, ch in enumerate(lst):
                if ch == 'a': lst[i] = 'b'
                elif ch == 'b': lst[i] = 'a'
            x, y = y, x
            s = ''.join(lst)
        ans = 0
        i = 0
        while (i < n):
            while i < n and s[i] != 'a' and s[i] != 'b': # skip non a and b
                i += 1
            cnt_a = cnt_b = 0
            while i < n and (s[i] == 'a' or s[i] == 'b'):
                if s[i] == 'a':
                    cnt_a += 1
                else:
                    if cnt_a > 0:
                        ans += x
                        cnt_a -= 1
                    else:
                        cnt_b += 1
                i += 1
            ans += min(cnt_a, cnt_b) * y
        return ans

class Solution {
public:
    int maximumGain(string s, int x, int y) {
        int n = s.size();
        if (x < y) {
            for (int i = 0; i < n; i++) {
                if (s[i] == 'a') s[i] = 'b';
                else if (s[i] == 'b') s[i] = 'a';
            }
            swap(x, y);
        }
        int i = 0, ans = 0;
        while (i < n) {
            while (i < n && s[i] != 'a' && s[i] != 'b') i++;
            int cnt_a = 0, cnt_b = 0;
            while (i < n && (s[i] == 'a' || s[i] == 'b')) {
                if (s[i] == 'a') cnt_a++;
                else {
                    if (cnt_a > 0) {
                        ans += x;
                        cnt_a--;
                    } else {
                        cnt_b++;
                    }
                }
                i++;
            }
            ans += min(cnt_a, cnt_b) * y;
        }
        return ans;
    }
};

---

寫在最後

Cover photo is remixed from @吃肥皂泡泡, thanks for their work!