2021-01-08] Longest Substring Without Repeating Characters

오늘의 문제:

leetcode.com/explore/challenge/card/january-leetcoding-challenge-2021/579/week-1-january-1st-january-7th/3595/

이번 문제는 한줄이지만, 한마디론 표현이 잘안되니 예시를 보며 이야기해보자.

<예시 1~4>

 

input값으로 문자열이 주어지고, 이 안에서 중복되는 값이 없는 substring의 최대 길이를 구하는 것이 문제이다.

 

예시 1처럼 "abcabcbb" 라면  "abc","bca","cab"가 가장 긴 substring이고 최대 길이는 3이다

 

문제풀이 )

 

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        maxval=1
        if s == "":
            return 0
        if len(s) == 1:
            return 1
        prechar=s[0]
        checked_idx=0
        for idx in range(1,len(s)): # 1~마지막까지
            temp=s[idx] # 현재의 문자
            if temp in s[checked_idx:idx]: # 현재 문자가 현재까지의 체크하지않은 문자열안에 존재하면
                if idx-checked_idx+1 > maxval: # 지금까지의 substring 길이가 maxval보다 크면 maxval 변경
                    maxval=idx-checked_idx
                if temp == prechar: # 현재 문자와 이전 문자가 동일하면 index값 동기화
                    checked_idx=idx
                else:
                    index = s[checked_idx:idx].index(temp)
                    checked_idx=checked_idx+index+1
            prechar=temp
        if len(s[checked_idx:]) > maxval:
            maxval=len(s[checked_idx:])
        return maxval