用 Python 编写程序来查找最长连续递增子字符串的长度

pythonserver side programmingprogramming更新于 2026/1/23 10:20:17

假设我们有一个小写字符串 s。它包含英文字母以及"?"符号。对于每个"?"，我们必须将其删除或用任何小写字母替换。我们必须找到以字母"a"开头的最长连续递增子字符串的长度。

因此，如果输入为 s = "vta???defke"，则输出将为 6，因为我们可以将 s 转换为"vtabcdefke"和"abcdef"是最长的连续递增子字符串，并且它也以"a"开头。

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

maxlen := 0
length := 0
qmarks := 0
对于 s 中的每个 c，执行
- 如果 c 与"?"相同，则
  - qmarks := qmarks + 1
- 否则，
  - idx := (c 的 ASCII) - ("a"的 ASCII)
  - 如果 length <= idx <= length + qmarks 或 idx，则 length := idx + 1 <= qmarks，否则为 0
  - qmarks := 0
- maxlen := maxlen 的最大值和 (length + qmarks 和 26 的最小值)
返回 maxlen

示例

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

def solve(s):
   maxlen = length = qmarks = 0
   for c in s:
      if c == "?":
         qmarks += 1
      else:
         idx = ord(c) - ord("a")
         length = idx + 1 if length <= idx <= length + qmarks or idx <= qmarks else 0
         qmarks = 0
      maxlen = max(maxlen, min(length + qmarks, 26))
   return maxlen

s = "vta???defke"
print(solve(s))