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

pythonserver side programmingprogramming

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

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

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

cur_max:= -1
res:= 空字符串
对于范围从 0 到 s 大小的 i，执行
- c := s[i]
- upper := 一个新的集合
- lower := 一个新的集合
- 如果 c 是小写，则
  - 将 c 添加到 lower
- 如果 c 是大写，则
  - 将 c 添加到大写但先将其转换为小写
- 对于 i+1 到 s 大小范围内的 j，执行
  - c := s[j]
  - 如果 c 是小写，则
    - 将 c 添加到小写中
  - 如果 c 是大写，则
    - 将 c 添加到大写但先将其转换为小写
  - 如果大写与小写相同，则
    - 如果 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))