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 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告