[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)