Pythonで連続して増加する最長の部分文字列の長さを見つけるプログラム

小文字の文字列sがあるとします。これには、英語の文字と「？」が含まれますシンボル。 「？」ごとに削除するか、小文字に置き換える必要があります。文字「a」で始まる、連続して増加する最長の部分文字列の長さを見つける必要があります。

したがって、入力がs ="vta ??? defke"の場合、出力は6になります。これは、sを "vtabcdefke"に変換でき、 "abcdef"は、連続して増加する最長の部分文字列であり、これも次のように始まります。 「a」。

これを解決するには、次の手順に従います-

• maxlen：=0
• 長さ：=0
• qmarks：=0
• sの各cについて、
  • cが「？」と同じ場合、
    • qmarks：=qmarks + 1
  • それ以外の場合、
    • idx：=（cのASCII）-（ "a"のASCII）
    • length：=idx + 1 if length <=idx <=length+qmarksまたはidx<=qmarks else 0
    • qmarks：=0
  • maxlen：=maxlenの最大値と（長さの最小値+ 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