Python程式：查詢兩個相同字元之間最長的子字串

假設我們有一個字串 s，我們需要找到兩個相同字元或元素之間最長的子字串的長度，不包括這兩個字元。如果找不到這樣的子字串，則返回 -1。

因此，如果輸入類似於 s = "level"，則輸出將為 3，因為最佳子字串可以是 "lev" 或 "vel"。

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

  • memo := 一個新的對映

  • 對於 i 從 0 到 s 的大小 - 1，執行以下操作：

    • 如果 s[i] 在 memo 中，則

      • 將 i 插入到 memo[s[i]] 的末尾

    • 否則，

      • memo[s[i]] := 一個只包含一個元素 i 的列表

  • best := 0

  • 對於 memo 中的每個鍵，執行以下操作：

    • best := best 和 (memo[key] 的最後一個元素 - memo[key] 的第一個元素) 的最大值

  • 返回 best - 1

示例 (Python)

 即時演示

def solve(s):
   memo = {}
   for i in range(len(s)):
      if s[i] in memo:
         memo[s[i]].append(i)
      else:
         memo[s[i]] = [i]

   best = 0
   for key in memo:
      best = max(best, memo[key][-1] - memo[key][0])
   return best - 1

s = "level"
print(solve(s))

輸入

"level"

輸出

3

更新於: 2021年5月17日

204 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告