Python에서 가장 긴 멋진 부분 문자열을 찾는 프로그램

<시간/>

숫자 문자열 s가 있다고 가정합니다. 우리가 알고 있는 것처럼 멋진 부분 문자열은 s의 비어 있지 않은 부분 문자열이므로 회문을 만들기 위해 얼마든지 교환할 수 있습니다. s의 최대 길이 굉장한 부분 문자열의 길이를 찾아야 합니다.

따라서 입력이 s ="4353526"과 같으면 "35352"가 가장 긴 멋진 부분 문자열이기 때문에 출력은 5가 됩니다. "35253" 회문을 만들 수 있습니다.

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

n :=0
pos_map :=키가 0이고 해당 값이 s의 크기를 포함하는 맵
max_len :=1
범위 크기가 s - 1에서 0인 i에 대해 1만큼 감소, 수행
- n :=n XOR (2^s[i])
- n이 pos_map에 있으면
  - max_len :=max_len 및 pos_map[n]-i의 최대값
- 0에서 9 사이의 j에 대해 수행
  - m :=n XOR 2^j
  - m이 pos_map에 있으면
    - max_len :=max_len 및 pos_map[m]-i의 최대값
- n이 pos_map에 없으면
  - pos_map[n] :=i
max_len 반환

예시

더 나은 이해를 위해 다음 구현을 살펴보겠습니다.

def solve(s):
   n = 0
   pos_map = {0:len(s)}

   max_len = 1

   for i in range(len(s)-1, -1, -1):
      n = n ^ (1 << int(s[i]))

      if n in pos_map:
         max_len = max(max_len, pos_map[n]-i)

      for j in range(10):
         m = n ^ (1 << j)
         if m in pos_map:
            max_len = max(max_len, pos_map[m]-i)

      if n not in pos_map:
         pos_map[n] = i

   return max_len

s = "4353526"
print(solve(s))

입력

"4353526"