[LeetCode] 3. Longest Substring Without Repeating Characters

Problem

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

Example 1:

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

Example 2:

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

Example 3:

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

Constraints:

• 0 <= s.length <= 5 * 10^4
• s consists of English letters, digits, symbols and spaces.

Solution

Approach

1. 문자열의 첫 문자부터 탐색하며 중복되지 않는 문자열의 최대 길이를 메모한다.

2. 중복되는 문자가 등장하면 직전에 중복 문자가 등장했던 위치의 뒤 혹은 현재 계산 중인 문자열의 시작 위치 중 큰 값의 위치로 계산 시작 위치를 옮긴다.

3. 위 과정을 반복하여 최대 길이를 반환한다.

Algorithm

Complexity Analysis

• Time Complexity

while반복문(5)은 문자열 s의 길이(n)와 반드시 동일한 횟수로 실행되므로 모든 경우에 O(n)의 시간 복잡도를 가진다.

• Space Complexity

최악(Worst) : 문자열 s내에 중복되는 문자가 없는 경우 map은 문자열 s의 길이(n)와 같은 크기의 map이 생성되므로 O(n)의 공간 복잡도를 가진다.

평균(Average) : 문자열 s내에 중복되는 문자와 그렇지 않은 문자가 절반씩 존재하는 경우 map은 문자열 s의 길이(n)의 절반에 해당하는 크기를 가지므로 O(n)의 공간 복잡도를 가진다.

최선(Best) : 문자열 s가 모두 동일한 문자로 이루어진 경우 map은 1만큼의 크기로 생성되므로 O(1)의 공간 복잡도를 가진다.