[LeetCode] Longest Substring Without Repeating Characters

문제

Given a string, find the length of the longest substring without repeating characters.

Example 1:

Input: "abcabcbb" Output: 3 Explanation: The answer is "abc", with the length of 3.

Example 2:

Input: "bbbbb" Output: 1 Explanation: The answer is "b", with the length of 1.

Example 3:

Input: "pwwkew" Output: 3 Explanation: The answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

 

Approach

Brute Force로 문자열 첫글자부터 읽어나가다 중복글자 나오면 스톱

그리고 다음글자부터 다시 읽어나가다 중복글자 나오면 스톱

문자열 끝까지 그렇게 찾아가는 심플한 구현 O(n^3) -> 하위 30퍼로 느림

sliding window로 O(n)으로 다시 구현했는데 더느림...

 

Optimization

Sliding window를 잘 구현해보자

추가: 기존 sliding window의 문제는 중복으로 나타나는 문자의 앞쪽 이전을 전부 안 읽은 것으로 처리하는 과정에서

문자열이 길어지면 오버헤드가 엄청나게 발생했는데

물리적으로 배열에 안 읽은 것으로 처리하는 것이 아닌, 읽어들이기 시작한 지점보다 작은 인덱스가 나올 경우

그냥 무시하고 업데이트 해버리는 것으로 바꿨더니 확 빨라졌다. (상위 0.7%)

 

Code

https://github.com/chi3236/algorithm/blob/master/LeetCode_LongestSubstringWithoutPepeatingCharacters_NSquare.cpp

chi3236/algorithm

https://github.com/chi3236/algorithm/blob/master/LeetCode_LongestSubstringWithoutPepeatingCharacters_slow.cpp

chi3236/algorithm

https://github.com/chi3236/algorithm/blob/master/LeetCode_LongestSubstringWithoutPepeatingCharacters_fast.cpp

chi3236/algorithm