3. Longest Substring Without Repeating Characters (LeetCode, Javascript)
이 문제는 문자의 패턴 중 동일 문자가 없도록 하는 가장 긴 서브셋을 찾는 문제입니다.
간단하게 앞에서부터 탐색해가면서 문제를 풀 수 있습니다.
다만 주의할 점은 abcbead 라는 String이 있는 경우 2번째 b를 만나는 지점에서 abcbead 이렇게 분리를 하게 된다면, 정답을 찾기 어렵습니다.
이를 해결하기 위해 슬라이딩 윈도우나 투 포인터 방식과 같이 두 개의 포인터를 사용하여 탐색 해 나가면 되며, 이를 HashMap을 이용하는 방식으로 응용할 수 있습니다.
자세한 설명은 아래에서 계속하겠습니다.
* Problem
Given a string s, find the length of the longest substring without repeating characters.
* 문자열 s 가 주어지고, 이 문자열 중 중복된 문자가 없는 가장 긴 substring을 찾아라~!
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 * 104
- s consists of English letters, digits, symbols and spaces.
* Solution 1. 투 포인터 (Two-Pointer) 이용
문제에서 주어진 문자열은 Set으로 표현하였으며, 두 개의 포인터는 Right(빨간색), Left(파란색) 라는 이름으로 표현하였습니다.
Right는 Set을 탐색해 나갈 때 사용하는 현재 위치를 표시하는 역할을 하고, Left는 Substring의 시작 위치를 표시합니다.
처음 시작을 하면, Right와 Left는 모두 첫번째 항목을 가르키며, Right가 가르키는 문자와 동일한 문자가 Substring에 있을 때 까지 반복합니다.
Right가 가르키는 항목의 문자가 Substring에 포함된 문자인 경우, Substring의 길이를 기존 최대길이와 비교하여 갱신하고, Left를 Right가 가르키는 항목의 문자와 동일한 문자의 다음 항목을 가르키도록 이동시킵니다.
이후 동일한 방법으로 Right가 가르키는 문자와 동일한 문자가 Substring에 있을 때 까지 반복합니다.
Set의 모든 항목에 대해 Right가 탐색을 마치게 되면, 현재 Subset의 길이도 최대 길이와 비교 후 갱신 합니다.
이를 통해 최대길이의 Substring을 찾을 수 있으며, Set을 처음 부터 끝까지 1번만 순회하므로 O(n)의 시간복잡도만으로 정답을 찾을 수 있습니다.
(코드 생략)
* Solution 2. HashMap 사용
위의 투 포인터 문제풀이 컨셉과 유사한 방식으로 해시맵을 사용하여 해결할 수 있습니다. 해시맵을 사용하게 되면 매 반복마다 비교하는 Substring내의 문자 탐색을 훨씬 효율적으로 처리할 수 있습니다.
아래 그림과 같이 Right 를 포인터로 이용하고, Left는 현재 Substring의 시작 index로 놓고 시작합니다.
핵심 Idea
- Loop를 수행하면서, Hashmap에 현재 항목 (Right가 가르키고 있는 문자) 이 포함되어있는지 확인하면서 Set을 탐색
첫 Phase (Right : 0) 에서는 a 가 있으며, a 는 HashMap에 존재하지 않아 현재의 index를 넣은 후 다음 Phase로 이동합니다.
Phase2, Phase3 에서도 마찬가지로 HashMap에 b, c가 존재하지 않아 현재 Right의 index를 넣은 후 다음 Phase로 이동합니다.
Phase 4 에서는 Right가 가르키고 있는 문자 b 가 HashMap에 존재 하므로, Substring이 성립할 수 없습니다. 따라서, 이전 Substring의 길이를 MaxLength에 반영한 후, 다음 Substring을 위해 Left의 위치를 변경합니다. ( 0 -> 2)
또한, HashMap이 가지고 있는 b 의 값을 Right의 index 값으로 변경합니다.
Phase 5 에서는 HashMap에 e가 존재 하지 않아, e를 HashMap에 추가 시키고 다음 Phase로 이동합니다.
Phase 6 에서는 Right가 문자 a를 가르키고 있으며, HashMap에는 a 항목이 이미 존재하고 있습니다. 하지만, a의 값이 0이고, 이는 0번째 index에 마지막 a가 있었다는 의미였으며, Left의 값은 2 이므로 Substring이 여전히 유효합니다. 따라서 HashMap의 a는 5로 값을 변경시킨 후 다음 Phase로 넘어갑니다.
위와 같은 방법으로 반복을 하다보면 Set을 모두 순회하게 됩니다. 마지막으로 Substring을 MaxLength에 반영하면 문제를 마무리 할 수 있습니다.
* Source Code
/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function(s) {
const map = new Map();
let maxLength = 0;
let left = 0, right = 0;
s.split('').forEach( c => {
const index = map.get(c);
if(index !== undefined && index >= left) {
maxLength = Math.max(right-left, maxLength);
left = index + 1;
}
map.set(c, right);
right++;
})
return Math.max(right-left, maxLength);
};이 문제에서는 2개의 포인트를 활용하여 Substring을 탐색해 나가면서 문제를 어렵지 않게 풀 수 있었으며, HashMap을 활용해 보다 효율적으로 계산할 수 있었습니다.