Python程式：查詢最長連續遞增子字串

假設我們有一個小寫字串 s。它包含英文字母以及“？”符號。對於每個“？”，我們必須將其刪除或替換為任何小寫字母。我們需要找到以字母“a”開頭的最長連續遞增子字串的長度。

因此，如果輸入類似於 s = "vta???defke"，則輸出將為 6，因為我們可以將 s 轉換為 "vtabcdefke"，而 "abcdef" 是最長的連續遞增子字串，並且它也以 "a" 開頭。

為了解決這個問題，我們將遵循以下步驟：

• maxlen := 0
• length := 0
• qmarks := 0
• 對於 s 中的每個字元 c，執行以下操作：
  • 如果 c 等於“？”，則：
    • qmarks := qmarks + 1
  • 否則：
    • idx := (c 的 ASCII 碼) - (“a” 的 ASCII 碼)
    • length := 如果 length <= idx <= length + qmarks 或 idx <= qmarks 則為 idx + 1，否則為 0
    • qmarks := 0
  • maxlen := maxlen 和 (length + qmarks 和 26 的最小值) 的最大值
• 返回 maxlen

示例

讓我們看看以下實現以獲得更好的理解：

def solve(s):
   maxlen = length = qmarks = 0
   for c in s:
      if c == "?":
         qmarks += 1
      else:
         idx = ord(c) - ord("a")
         length = idx + 1 if length <= idx <= length + qmarks or idx <= qmarks else 0
         qmarks = 0
      maxlen = max(maxlen, min(length + qmarks, 26))
   return maxlen

s = "vta???defke"
print(solve(s))

輸入

"vta???defke"

輸出

6

Arnab Chakraborty

更新於: 2021年10月19日

189 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

立即開始