파이썬에서 반복 문자가 없는 가장 긴 부분 문자열

문자열이 있다고 가정합니다. 문자를 반복하지 않고 가장 긴 부분 문자열을 찾아야 합니다. 따라서 문자열이 "ABCABCBB"와 같으면 길이가 3인 반복되는 부분 문자열이 있으므로 결과는 3이 됩니다. 이것이 "ABC"입니다.

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

• set i :=0, j :=0, 정보를 저장할 하나의 맵 설정
• ans :=0
• while j <문자열 길이 s
  • s[j]가 지도에 없거나 i> map[s[j]]이면
    • ans :=max(ans, j – i + 1)
    • 지도[s[j]] :=j
  • 그렇지 않으면
    • i :=지도[s[j]] + 1
    • ans :=max(ans, j – i + 1)
    • j를 1 감소
  • j를 1 증가
• 반환

예제(Python)

이해를 돕기 위해 다음 구현을 살펴보겠습니다.

class Solution(object):
   def lengthOfLongestSubstring(self, s):
      i =0
      j = 0
      d={}
      ans = 0
      while j < len(s):
         if s[j] not in d or i>d[s[j]]:
            ans = max(ans,(j-i+1))
            d[s[j]] = j
         else:
            i = d[s[j]]+1
            ans = max(ans,(j-i+1))
            j-=1
         #print(ans)
         j+=1
      return ans
ob1 = Solution()
print(ob1.lengthOfLongestSubstring("ABCABCBB"))

입력

"ABCABCBB"

출력

3