leetcode: 3. Longest Substring Without Repeating Characters JS solution

https://leetcode.com/problems/longest-substring-without-repeating-characters/

Longest Substring Without Repeating Characters - LeetCode

 

🔒 문제

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 * 104
• s consists of English letters, digits, symbols and spaces.
  
  

---

🔑 풀이

문제 접근 방법:

위와 같이 정해진 하나의 배열에서 가장 긴 substring을 찾는 문제는 투포인터, 슬라이딩 윈도우로 풀 수 있다.

 

1) substring의 가장 긴 길이

 

문제는 중복이 없는 가장 긴 substring의 길이를 반환하는 것이다.

중복이 없는 가장 긴 길이를 구한다는 것에서 가장 긴 길이를 어떻게 구할 수 있을까:

 

전체 string에서 순서대로 하나씩 증가하며

중복이 없는 substring까지 계속해서 length가 증가하다가,

중복되는 기점에서 중복 조건에 의해 substring이 다시 정의되고

해당 substring의 길이와 현재까지의 가장 긴 length의 길이를 비교하여

 

구해진 length가 가장 긴 길이의 substring의 길이가 될 것이다.

 

2) 중복 조건

 

중복이라는 것을 어떻게 알 수 있을까

 

내가 가지고 있는 substring 은 loop를 돌며 만났던 char 들의 집합이다.

 

그렇다면 해당 char과 같은 char이 substring에 있는가를 확인하기 위해서는 해당 char와 index를 가지고 있어야 한다.

 

<char, index> 형태의 객체를 저장해 놓았다가 

 

현재 char가 중복 확인을 위한 객체 <char, index> 객체 내에 있는가를 조건문으로 만들어서 분기를 만들어 주면 된다.

 

위와 같은 객체를 나타내기 위해 JS Map 객체를 사용했다.

 

3) 중복 체크

 

우선 new Map() 연산으로 새로운 map 객체를 생성하고,

해당 객체에는

Map(size) { <char> => <index>, <char> => <index>, <char> => <index>, ...}

형태이다.

 

loop를 돌며 현재 위치한 index의 char를 저장하고

 

해당 map에 char이 이미 존재하는지를 조건문으로 하여 중복 체크를 해줄 수 있다.

 

4) 중복 조건에 따른 행동

 

그렇다면 현재 char가 중복되었다면 어떻게 할까?

 

현재 char이 중복되었다면

 

새로운 substring에 대한 length를 갱신해주어야 할 것이다.

 

🍯 팁

새로운 substring은?

기존 substring이 아닌 현재 char과 중복되는 char의 index + 1 에서부터 다시 계산될 substring을 의미한다.

우리는 중복되지 않는 가장긴 substring을 구해야하기 때문에

중복된 부분부터 다시 계산하여 가장 긴 길이를 구해야 한다.

 

예를 들어

pwwkew 라는 string이 주어졌다면

 

헷갈릴 수 있는게 현재 substring + 1 부터가 아니라, 중복된 char + 1 부터이다.

다른 예제 baba를 보면 두번째 b가 0번쨰 b와 중복됙기 때문에

0번째 + 1 부터 다시 substring이 만들어지는 것이다.

 

위와 같이 접근하여 중복 조건을 기점으로 새로운 substring의 길이를 구할 수 있다는 것을 알았다.

 

💡 해결

이제 슬라이딩 윈도우 알고리즘으로 이를 O(n)으로 해결할 수 있다.

 

left, right라는 two points를 가지고 right++ loop를 돌면서 substring을 만들어가고 그에 따른 length를 업데이트할 수 있다,

중복된 값을 만나면 left를 중복된 char의 index+1를 해주어 새로운 substring의 0 번째 index를 생신해준다.

 

🍯 팁

그러나 char의 중복된 index를 left로 해줄 때 주의해야하는 부분이 있다.

 

예를 들어 abba 라는 string이 주어졌을 때,

 

map을 보면

 

1. s[0]: a

map(1) { a: 0 }

left: 0, right: 1

length: 1

 

2. s[1]: b

map(2) { a: 0, b: 1}

left: 0, right: 2

length: 2

 

3. s[2]: a

map{2): {a: 0, b: 1}

left: 1, right: 3

legnth: 3 

 

위와 같은 오류가 날 수 있다.

원래는 3.에서도 left가 2가되어야 한다.

 

이유는 우리가 중복의 조건으로 현재 char의 중복된 index+1 이기 때문에

이를 a에 대입해보면 a의 중복된 index는 0,여기에 +1 을 해주면 1이된다.

 

이러렇게 포인터가 뒤로 가는 것을 방지하기 위해서

 

left: max(left, 중복된char의 index + 1)이 되어야 한다.

 

 

 

💻 코드

var lengthOfLongestSubstring = function(s) {
    let left = 0, right = 0, length = 0;
    let stringMap = new Map();
    while (right < s.length) {
        if (stringMap.has(s[right])) {
            left = Math.max(stringMap.get(s[right]) + 1, left);
        }
        stringMap.set(s[right], right);
        length = Math.max(right - left + 1 , length);
        right++;
    }
    return length;
};