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

小松鼠-avatar-img
發佈於演算法題目解析 個房間
更新於 發佈於 閱讀時間約 6 分鐘

題目敘述 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)框架示意圖

raw-image

滑動窗口(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

avatar-img
90會員
425內容數
由有業界實戰經驗的演算法工程師, 手把手教你建立解題的框架, 一步步寫出高效、清晰易懂的解題答案。 著重在讓讀者啟發思考、理解演算法,熟悉常見的演算法模板。 深入淺出地介紹題目背後所使用的演算法意義,融會貫通演算法與資料結構的應用。 在幾個經典的題目融入一道題目的多種解法,或者同一招解不同的題目,擴展廣度,並加深印象。
留言0
查看全部
avatar-img
發表第一個留言支持創作者!
給定一個輸入非負整樹陣列nums,請找出k值,使得陣列中恰好有k個元素大於等於 k。如果無解,回傳-1。尋找k值的方法包括排序法和二分搜尋法,時間複雜度都為O(n log n),空間複雜度為O(1)。關鍵知識點是當解空間具有遞增或遞減的性質時,可以用二分搜尋法加快搜尋效率。
探討如何使用DP動態規劃的方法來進行單字串接,包含了DP遞迴關係式、狀態定義、優化技巧和程式碼示例。同時分析了時間複雜度、空間複雜度和關鍵知識點。這是LeetCode的一個應用題,類似於Word Break I的延伸。
知道如何從一組給定的英文字母和單字庫中的單字拼出最高分的單字組合。使用DFS + 回溯法 + 剪枝優化的演算法,詳細分析瞭如何展開所有可能的路徑,並且找出符合條件的狀態,協助讀者理解演算法背後的思維和方法。
本篇文章介紹了區間DP及博弈論Min/Max最佳化的相關概念,以及如何應用這些概念來計算最佳策略進行取石頭遊戲的模擬。文章實際分析了演算法、實用的加速技巧和關鍵知識點。這篇文章對於想要學習區間DP的讀者來說非常有價值。
子集合生成是一道經典的組合類上機考和面試題目。本篇文章介紹多個不同的解決方案,以及相關演算法框架。主要目標是給定n個相異的元素,產生所有的子集合。
這篇文章,會帶大家快速回顧DFS+回溯法框架(還沒看過或想複習的可以點連結進去)。 用DFS+回溯法框架,解開 直線排列Permutations 的全系列題目。 幫助讀者鞏固DFS+回溯法框架這個重要的知識點。 回顧 DFS+回溯法框架 白話的意思 # 列舉所有可能的情況,遞迴展開所有分
給定一個輸入非負整樹陣列nums,請找出k值,使得陣列中恰好有k個元素大於等於 k。如果無解,回傳-1。尋找k值的方法包括排序法和二分搜尋法,時間複雜度都為O(n log n),空間複雜度為O(1)。關鍵知識點是當解空間具有遞增或遞減的性質時,可以用二分搜尋法加快搜尋效率。
探討如何使用DP動態規劃的方法來進行單字串接,包含了DP遞迴關係式、狀態定義、優化技巧和程式碼示例。同時分析了時間複雜度、空間複雜度和關鍵知識點。這是LeetCode的一個應用題,類似於Word Break I的延伸。
知道如何從一組給定的英文字母和單字庫中的單字拼出最高分的單字組合。使用DFS + 回溯法 + 剪枝優化的演算法,詳細分析瞭如何展開所有可能的路徑,並且找出符合條件的狀態,協助讀者理解演算法背後的思維和方法。
本篇文章介紹了區間DP及博弈論Min/Max最佳化的相關概念,以及如何應用這些概念來計算最佳策略進行取石頭遊戲的模擬。文章實際分析了演算法、實用的加速技巧和關鍵知識點。這篇文章對於想要學習區間DP的讀者來說非常有價值。
子集合生成是一道經典的組合類上機考和面試題目。本篇文章介紹多個不同的解決方案,以及相關演算法框架。主要目標是給定n個相異的元素,產生所有的子集合。
這篇文章,會帶大家快速回顧DFS+回溯法框架(還沒看過或想複習的可以點連結進去)。 用DFS+回溯法框架,解開 直線排列Permutations 的全系列題目。 幫助讀者鞏固DFS+回溯法框架這個重要的知識點。 回顧 DFS+回溯法框架 白話的意思 # 列舉所有可能的情況,遞迴展開所有分
你可能也想看
Google News 追蹤
Thumbnail
隨著理財資訊的普及,越來越多台灣人不再將資產侷限於台股,而是將視野拓展到國際市場。特別是美國市場,其豐富的理財選擇,讓不少人開始思考將資金配置於海外市場的可能性。 然而,要參與美國市場並不只是盲目跟隨標的這麼簡單,而是需要策略和方式,尤其對新手而言,除了選股以外還會遇到語言、開戶流程、Ap
Thumbnail
嘿,大家新年快樂~ 新年大家都在做什麼呢? 跨年夜的我趕工製作某個外包設計案,在工作告一段落時趕上倒數。 然後和兩個小孩過了一個忙亂的元旦。在深夜時刻,看到朋友傳來的解籤網站,興致勃勃熬夜體驗了一下,覺得非常好玩,或許有人玩過了,但還是想寫上來分享紀錄一下~
Thumbnail
可能包含敏感內容
高中數學主題練習—指數比大小
Thumbnail
實際回測給各位參考~ 不過可操作空間還是很大,不一定要買收盤丟開盤喔~
Thumbnail
接下來喜特先生會介紹一系列關於文字處理時,會常常運用到的函式。我們這次先從比較簡單的 LEN、CHAR 和 REPT 開始,之後會陸續介紹其他的。如果你有什麼想要了解的函式,歡迎在下面留言告訴我! LEN:字元長度 我們可以用 LEN 函式取得儲存格或字元的長度。 語法相當簡單:
開花和上通道有什麼不同,操作上要注意什麼 個案心得與觀察: 3188鑫龍騰、6230尼得科超眾、3207耀勝、3005神基、5515建國、2527宏璟、3296勝德、3543州巧 QA:3081聯亞、3324雙鴻、3017奇鋐、2603長榮
Thumbnail
隨著理財資訊的普及,越來越多台灣人不再將資產侷限於台股,而是將視野拓展到國際市場。特別是美國市場,其豐富的理財選擇,讓不少人開始思考將資金配置於海外市場的可能性。 然而,要參與美國市場並不只是盲目跟隨標的這麼簡單,而是需要策略和方式,尤其對新手而言,除了選股以外還會遇到語言、開戶流程、Ap
Thumbnail
嘿,大家新年快樂~ 新年大家都在做什麼呢? 跨年夜的我趕工製作某個外包設計案,在工作告一段落時趕上倒數。 然後和兩個小孩過了一個忙亂的元旦。在深夜時刻,看到朋友傳來的解籤網站,興致勃勃熬夜體驗了一下,覺得非常好玩,或許有人玩過了,但還是想寫上來分享紀錄一下~
Thumbnail
可能包含敏感內容
高中數學主題練習—指數比大小
Thumbnail
實際回測給各位參考~ 不過可操作空間還是很大,不一定要買收盤丟開盤喔~
Thumbnail
接下來喜特先生會介紹一系列關於文字處理時,會常常運用到的函式。我們這次先從比較簡單的 LEN、CHAR 和 REPT 開始,之後會陸續介紹其他的。如果你有什麼想要了解的函式,歡迎在下面留言告訴我! LEN:字元長度 我們可以用 LEN 函式取得儲存格或字元的長度。 語法相當簡單:
開花和上通道有什麼不同,操作上要注意什麼 個案心得與觀察: 3188鑫龍騰、6230尼得科超眾、3207耀勝、3005神基、5515建國、2527宏璟、3296勝德、3543州巧 QA:3081聯亞、3324雙鴻、3017奇鋐、2603長榮