字串應用: 最少的操作讓字串平衡 Min Deletions Make String Balanced_LC #1653

Piret Ilver on Unsplash

題目敘述 Minimum Deletions to Make String Balanced

給定一個只會有包含'a'或'b'的輸入字串s。

每次操作可以任選一個字元刪除。
請問最少需要多少次操作，才會使得所有的'b'都在'a'後面?

測試範例

Input: s = "aababbab"
Output: 2
Explanation: You can either:
Delete the characters at 0-indexed positions 2 and 6 ("aababbab" -> "aaabbb"), or
Delete the characters at 0-indexed positions 3 and 6 ("aababbab" -> "aabbbb").

Example 2:

Input: s = "bbaaaaabb"
Output: 2
Explanation: The only solution is to delete the first two characters.
刪除前面兩個b，變成"aaaaabb"
使得所有的'b'都在'a'後面​

演算法 用stack刪除所有非法pair 'ba'

題目要求所有的b都在a的後面

也就是說，字串s中不允許出現'ba'這種非法pattern。

我們可以由左到右掃描每個字元，搭配stack去統計非法pair 'ba'的出現次數。

每一個非法pair 'ba'都需要一次刪除操作。

因此可以推導出一個結論: 最小的刪除操作 等於 非法pair 'ba'的數量

程式碼 用stack刪除所有非法pair 'ba'

class Solution:
    def minimumDeletions(self, s: str) -> int:

        cnt, stack = 0, []

        for char in s:
            if char == "a" and stack and stack[-1] == "b":
                # Delete a or b to remove a bad pair
                stack.pop()
                cnt += 1
            else:
                stack.append(char)
                
        return cnt

複雜度分析

時間複查度: O(n)

從左到右掃描每個字元，所需時間為O(n)

空間複查度: O(n)

建立一個stack，最多所需空間為O(n)

關鍵知識點

這邊用到的技巧類似於用stack去找出合法的()括號配對，強烈讀者一起複習這題高度關聯的類似題

Stack堆疊應用題 合法括號配對字串 Leetcode #20_Valid Parentheses

Reference

[1] Minimum Deletions to Make String Balanced - LeetCode