[leetcode-3] Longest Substring Without Repeating Characters

LeetCode-3

Longest Substring Without Repeating Characters : Given a string s, find the length of the longest substring without repeating characters.

note : s consists of English letters, digits, symbols and spaces.

Answer

        :::python

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if len(s)==1:
            return 1
        left, right, answer_max = 0, 1, 0
        for _ in range(len(s)):    
            while (left < right) and (right < len(s)):
                if s[right] in s[left:right]:
                    answer = right - left 
                    left += 1 
                    right = left+1
                    break
                else:
                    right += 1
                if right == len(s):
                    answer = right-left
                    break 
            if answer_max < answer:
                answer_max = answer
        return answer_max

Result : 878ms Memory: 14mb

## Longest Substring Without Repeating Characters

Longest Substring Without Repeating Characters는 중복되지 않는 문자열의 최대 길이를 찾는 알고리즘이다.

알고리즘 설명

이 알고리즘은 sliding window 알고리즘을 사용하여 구현할 수 있다. 첫번째 인덱스와 마지막 인덱스를 가리키는 두 개의 포인터(또는 인덱스)를 사용하여 중복이 없는 부분 문자열을 찾을 수 있다.

두 개의 포인터를 사용하여 문자열을 탐색하면서 새로운 문자를 발견했을 때는 해당 문자의 인덱스를 기억하고, 중복되는 문자를 발견했을 때는 첫 번째 포인터를 중복된 문자 다음 인덱스로 옮긴다. 이제 두 번째 포인터와 첫 번째 포인터 사이의 문자열이 중복되지 않는 가장 긴 부분 문자열이다.

시간 복잡도

이 알고리즘의 시간 복잡도는 O(n)이다. 포인터를 이동시키면서 문자열을 한 번만 탐색하기 때문에 탐색 시간은 문자열의 길이와 비례한다.

예시

입력: "abcabcbb"
출력: 3 (abc)

입력: "bbbbb"
출력: 1 (b)

입력: "pwwkew"
출력: 3 (wke)