Pythonで2つの等しい文字の間の最大の部分文字列を見つけるプログラム

文字列sがあるとすると、2つの文字を除いて、2つの等しい文字または要素の間の最長の部分文字列の長さを見つける必要があります。そのような部分文字列が見つからない場合は、-1を返します。

したがって、入力がs ="level"のような場合、最適なサブストリングは"lev"または"vel"のいずれかであるため、出力は3になります。

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

• メモ：=新しい地図

• 0からs-1のサイズのiの場合、実行します

  • s [i]がメモにある場合、

    • メモの最後にiを挿入[s[i]]

  • それ以外の場合

    • memo [s [i]]：=1つの要素のみを含むリストi

• 最高：=0

• メモのキーごとに、実行します

  • best：=bestの最大値と（memo[key]の最後の要素-memo[key]の最初の要素）

• 最高のリターン-1

例（Python）

def solve(s):
   memo = {}
   for i in range(len(s)):
      if s[i] in memo:
         memo[s[i]].append(i)
      else:
         memo[s[i]] = [i]

   best = 0
   for key in memo:
      best = max(best, memo[key][-1] - memo[key][0])
   return best - 1

s = "level"
print(solve(s))

入力

"level"

出力

3