Leetcode Python - 3. Longest Substring Without Repeating Characters

Leetcode #3 - Longest Substring Without Repeating Characters

이제 blind 75 leetcode를 풀어보겠습니다. https://leetcode.com/discuss/interview-question/460599/Blind-75-LeetCode-Questions

리트코드의 문제 3 ‘Longest Substring Without Repeating Characters’을 파이썬으로 풀어 보도록 하겠습니다.

discuss 참고 포인트는 slicing window 패턴을 이용해 풀 수 있습니다.

전체 코드는 아래와 같습니다.

class Solution:
    def lengthOfLongestSubstring(self, s):
        start = maxLength = 0
        usedChar = {}

        for i,c in enumerate(s):
            if c in usedChar and start <= usedChar[s[i]]:
                start = usedChar[c] + 1
            else:
                maxLength = max(maxLength, i - start + 1)
            usedChar[c] = i

        return maxLength

시간복잡도는

• O(n) : 한번의 loop

공간복잡도는

• O(1) : 상수 선언