使用 Python 查找最长 Nice 子字符串的程序

假设我们有一个字符串 s。我们必须找到 s 的最长 Nice 子字符串。对于一个字符串 s，当字母表中的每个字母在 s 中都以大写和小写两种形式出现时，它就被认为是 Nice 的。如果有多个这样的子字符串，则返回最早出现的子字符串。

因此，如果输入类似于 s = "ZbybBbz"，则输出将为 "bBb"，因为它包含小写和大写 B。

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

  • cur_max:= -1

  • res:= 空字符串

  • 对于 i 从 0 到 s 的大小，执行以下操作

    • c := s[i]

    • upper := 一个新的集合

    • lower := 一个新的集合

    • 如果 c 是小写，则

      • 将 c 添加到 lower 中

    • 如果 c 是大写，则

      • 将 c 添加到 upper 中，但在之前将其转换为小写

    • 对于 j 从 i+1 到 s 的大小，执行以下操作

      • c := s[j]

      • 如果 c 是小写，则

        • 将 c 添加到 lower 中

      • 如果 c 是大写，则

        • 将 c 添加到 upper 中，但在之前将其转换为小写

      • 如果 upper 等于 lower，则

        • 如果 j-i > cur_max，则

          • cur_max := j-i

          • res := s 从索引 i 到 j+1 的子字符串

  • 返回 res

让我们看看以下实现以获得更好的理解：

示例

 实时演示

def solve(s):
   cur_max= -1
   res=""
   for i in range(len(s)):
      c = s[i]
      upper = set()
      lower = set()
      if c.islower():
         lower.add(c)
      if c.isupper():
         upper.add(c.lower())
      for j in range(i+1,len(s)):
         c = s[j]
         if c.islower():
            lower.add(c)
         if c.isupper():
            upper.add(c.lower())
         if upper == lower:
            if j-i>cur_max:
               cur_max = j-i
               res = s[i:j+1]
   return res
s = "ZbybBbz"
print(solve(s))

输入

"ZbybBbz"

输出

bBb

更新于: 2021年5月29日

477 次查看

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告