LeetCode) lengthOfLongestSubstring

 

중복 되지 않는 가장 긴 문자열을 찾는 문제.

 

 

 

문자열을 n번 순회하고 해당 문자열의 길이를 하나씩 늘려가며 검사하는 로직 통과는 했지만 상당히 낮은 속도를 보여줬다.

from collections import Counter as ct
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        set_s = list(set(s))

        if len(set_s) == 0:
            return 0
        elif len(set_s) == 1:
            return 1

        max_result = len(set_s)
        result = 2

        for i in range(len(s)):
            if i + result > len(s):
                break
            flag = 0
            t1 = ct(s[i:i + result])
            t2 = True
            for j in t1.values():
                if j > 1:
                    t2 = False
            while t2:
                if len(t1.keys()) == max_result+1 or i + result > len(s):
                    flag = 1
                    break
                result += 1
                t1 = ct(s[i:i + result])
                for j in t1.values():
                    if j > 1:
                        t2 = False
            if flag == 1:
                break

        return result - 1

 

 

답안 코드는 매우 간결하고 속도가 빠르다. 똑같이 n번 순회하지만 일일히 하나씩 늘려가며 문자열을 검사하지 않고 순회하면서 길이를 책정한다. 한 번에 떠올리긴 힘들겠지만 충분히 생각해볼만한 방식인 것 같다.

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        used = {}
        max_len = start = 0
        for i in range(len(s)):
            if s[i] in used and start <= used[s[i]]:
                start = used[s[i]] + 1
            else:
                max_len = max(max_len, i - start + 1)

            used[s[i]] = i

        return max_len