Python에서 동일한 두 문자 사이에서 가장 큰 부분 문자열을 찾는 프로그램

<시간/>

문자열 s가 있다고 가정하고 두 문자를 제외하고 동일한 두 문자 또는 요소 사이에서 가장 긴 부분 문자열의 길이를 찾아야 합니다. 그러한 부분 문자열을 찾을 수 없으면 -1을 반환합니다.

따라서 입력이 s ="level"과 같으면 최적의 하위 문자열이 "lev" 또는 "vel"이 될 수 있으므로 출력은 3이 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

메모 :=새 지도
범위 0에서 s - 1까지의 i에 대해 수행
- s[i]가 메모에 있으면
  - 메모[s[i]]의 끝에 i 삽입
- 그렇지 않으면
  - 메모[s[i]] :=요소가 하나만 있는 목록 i
최고 :=0
메모의 각 키에 대해 수행
- best :=best의 최대값 및 (memo[key]의 마지막 요소 - 메모[key]의 첫 번째 요소)
최고 반환 - 1

예제(파이썬)

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"