Python程序：查找包含两个不同元素的最长子字符串

假设我们有一个字符串 s，我们需要找到包含最多两个不同字符的最长子字符串的长度。

因此，如果输入类似于 s = "xyzzy"，则输出将为 4，因为 "yzzy" 是包含最多 2 个唯一字符的最长子字符串。

为了解决这个问题，我们将遵循以下步骤：

  • start := 0

  • c := 一个映射

  • ans := 0

  • 对于 end 从 0 到 s 的大小，执行：

    • c[s[end]] := c[s[end]] + 1

    • 当 c 的大小 > 2 时，执行：

      • c[s[start]] := c[s[start]] - 1


      • 如果 c[s[start]] 为 0，则：

        • 删除 c[s[start]]

      • start := start + 1

    • ans := ans 和 (end - start + 1) 的最大值

  • 返回 ans

让我们看看下面的实现，以便更好地理解：

示例

 实时演示

class Solution:
   def solve(self, s):
      from collections import Counter
      start = 0
      c = Counter()
      ans = 0
      for end in range(len(s)):
         c[s[end]] += 1
         while len(c) > 2:
            c[s[start]] -= 1
            if not c[s[start]]:
               del c[s[start]]
            start += 1
         ans = max(ans, end - start + 1)
      return ans
ob = Solution()
s = "xyzzy"
print(ob.solve(s))

输入

s = "xyzzy"

输出

4

更新于： 2020年10月10日

516 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告