Python程序：查找最长连续递增子字符串

假设我们有一个小写字符串 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 := 如果 length <= idx <= length + qmarks 或 idx <= qmarks 则为 idx + 1，否则为 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))

输入

"vta???defke"

输出

6

Arnab Chakraborty

更新于: 2021年10月19日

189 次浏览

开启你的 职业生涯

通过完成课程获得认证

立即开始