字字珠璣 替換後，最長的相等子字串_滑動窗口應用_Leetcode #1208

Vipul Jha on Unsplash

題目敘述 Get Equal Substrings Within Budget

給定兩個字串s和t，還有對應的預算上限cost。
每修改一個字元就要付出對應的ASCII Code距離成本。
請問修改後s 和 t 最長的相等子字串長度是多少?

原文題目敘述

測試範例

Example 1:

Input: s = "abcd", t = "bcdf", maxCost = 3
Output: 3
Explanation: "abc" of s can change to "bcd".
That costs 3, so the maximum length is 3.
"abc"改成"bcd"耗費3單元的修改成本，​字串長度=3

Example 2:

Input: s = "abcd", t = "cdef", maxCost = 3
Output: 1
Explanation: Each character in s costs 2 to change to character in t,  so the maximum length is 1.
"a" 改成 "c" 耗費2單元的修改成本，接下來任何修改都會超過預算限制，字串長度=1

Example 3:

Input: s = "abcd", t = "acde", maxCost = 0
Output: 1
Explanation: You cannot make any change, so the maximum length is 1.
預算=0 代表無法做修改
原本相等的子字串只有"a" 長度=1

約束條件

Constraints:

• 1 <= s.length <= 10^5

輸入字串的長度介於1~十萬之間。

• t.length == s.length

輸入字串s和字串t長度相等

• 0 <= maxCost <= 10^6

預算上限介於0~一百萬之間，如果預算等於零，代表不允許修改。

• s and t consist of only lowercase English letters.

輸入字串只會有小寫英文字母。

觀察

題目說是修改後的最長相等子字串的長度。

也就是說，一定要是連續的某個區間，區間內處處相等。

原題目等價於:

連續的某個區間，區間內每個字元都相等，而且修改總成本<=最大預算。

聯想到可以用滑動窗口的框架 合縱連橫: 從滿足特定條件的區間 理解 滑動窗口 背後的本質來解。

滑動窗口(Sliding window)框架示意圖

滑動窗口(Sliding window)的框架

left = 0

# 右端點持續往右滑動，掃描每個元素​

for right, value in enumerate( array ):

		更新窗口資訊​

		while 為了滿足特定條件，窗口需要收縮時:

			收縮窗口
			更新窗口資訊
			left += 1


		現在滿足條件了，可以更新答案​

return 最終答案​

這題的窗口資訊是什麼?

當下窗口的大小 和 字元修改總成本。

特定條件是什麼?

窗口內的字元修改總成本必須 小於等於 總預算。

更新答案時，如何計算?

更新答案時，就是維護窗口大小的最大值=連續相等子字串的長度最大值。

演算法 滑動窗口

從左到右掃描每個字元，如果字元不同，就需要修改，這時候修改成本累加當下的ASCII Code距離。

如果修改總成本已經超過總預算了，
則收縮左窗口，一直到修改成本小於等於總預算內為止。

每回合動態更新窗口的最大值，也就是連續相等子字串的長度最大值。

程式碼 滑動窗口

class Solution:
    def equalSubstring(self, s, t, cost):
        
        # left endpoint of sliding window
        left = 0

        # current edit cost in sliding window
        cur_cost = 0

        # max length of valid sliding window = max length of equal substring
        max_length = 0

        # Scan each character
        for right in range( len(s ) ):
            
            # Update edit cost
            if s[right] != t[right]:
                cur_cost += abs(  ord(s[right]) - ord(t[right]) )
            
            # Shrink sliding window if current cost is over budget
            while cur_cost > cost:
                cur_cost -= abs(  ord(s[left]) - ord(t[left]) )
                left += 1
            
            # Update max length of valid sliding window = length of equal substring
            max_length = max(max_length, right-left+1)

        return max_length

複雜度分析

時間複雜度:O(n)

滑動窗口從左到右，掃描每個字元，每個字元最多檢查兩次(擴張一次，收縮一次)。

空間複雜度: O(1)

使用到的都是固定尺寸的臨時變數，為常數級別O(1)。

Reference

[1] Get Equal Substrings Within Budget - LeetCode