[LeetCode] 3. Longest Substring Without Repeating Characters

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

LeetCode - The World's Leading Online Programming Learning Platform

이 문제는 가장 간단하게 내가 풀 수 있었던 방법이 이중 반복문을 돌리며 범위를 잡고, {문자:0} 형태의 object를 만들어 특정 문자가 등장할 때마다 해당 키의 value값에 1씩 더해주는 식으로 중복 여부를 따졌다.

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function (s) {
  let numsObj = {};
  let newStr = '';
  let maxLenString = '';

  for (let i = 0; i < s.length; i++) {
    if (!Object.keys(numsObj).includes(s[i])) {
      let newObj = {
        [s[i]]: 0
      };
      numsObj = { ...numsObj, ...newObj };
    };
  }

  for (let i = 0; i < s.length; i++) {
    for (key in numsObj) {
      numsObj[key] = 0;
    }
    numsObj[s[i]] += 1
    for (let n = i; n < s.length; n++) {
      if (i !== n) {
        numsObj[s[n]] += 1
      }

      if (numsObj[s[i]] > 1) {
        break;
      }

      if (numsObj[[s[n]]] > 1) {
        break;
      }

      newStr = s.slice(i, n + 1);
      if (maxLenString.length < newStr.length) {
        maxLenString = newStr;
      }
    }
  }
  return maxLenString.length;
};

 

참고로 이걸 하면서 처음으로 ES6에서 문자열을 key로 하는 object 생성법을 알게 됐다.

// https://koonsland.tistory.com/146 참고

const key = 'key';
const value = 0;

const newObject = {
	[key] : value // 이런 식으로 [] 안에 문자열 변수를 넣어주면 문자를 key로 사용가능!ES6
}

//ES5까지는 이렇게 했다.
let newObject = {} // 빈 Object를 만들고
newObject[key] = value //여기에 대입해 사용

하지만 당연히 제대로 된 알고리즘을 사용하지 않았기에 시간은 많이 나왔다..

그래서 조금 더 빠르게 풀 수 있는(시간 복잡도가 무려 O(N)이다!) 풀이법을 확인해보았다.

출처: https://leetcode.com/problems/longest-substring-without-repeating-characters/solutions/2940314/javascript-true-o-n-sliding-window-with-explanation/

LeetCode - The World's Leading Online Programming Learning Platform

/**
 * @param {string} s
 * @return {number}
 */
function lengthOfLongestSubstring(inputString) {
    if (inputString.length == 0) return 0;

    let n = inputString.length;
    
    // starting index of current window substring
    let stCurr = 0,
        // length of the longest substring
        longest = 0,
        // length of the current substring (size of window)
        currLen = 0,
        // starting index of longest substring
        start = 0;

	// hashmap to store the element as key and index last seen as value
    let lastSeenAt = {};

    // Traverse inputString to find the longest substring
    // without repeating characters.
    for (index = 0; index < n; index++) {
        let val = inputString[index];

        // If the current element is not present in the hash map,
        // then store it in the hash map with the value as the current index.
        if (!(val in lastSeenAt)) lastSeenAt[val] = index;
        else {
            // If the current element is present in the hash map,
            // it means that this element may have appeared before.
            // Check if the current element occurs before or after `stCurr`.
            if (lastSeenAt[val] >= stCurr) {
                currLen = index - stCurr;
                if (longest < currLen) {
                    longest = currLen;
                    start = stCurr;
                }
                // The next substring will start after the last
                // occurence of the current element.
                stCurr = lastSeenAt[val] + 1;
            }

            // Update the last occurence of
            // the element in the hash map
            lastSeenAt[val] = index;
        }
    }

    // Update the longest substring's
    // length and starting index.
    if (longest < index - stCurr) {
        start = stCurr;
        longest = index - stCurr;
    }

    return longest;
};

위 문제는 stCurr이라는 시작지점을 이용해 끝 지점을 움직이며 가장 긴 중복없는 문자열을 찾는다. 여기서 나오는 개념이 바로 sliding window와 투 포인터이다.

슬라이딩 윈도우는 구간이 같을 경우, 처음 값을 빼고 끝 값을 더해주는 방식으로 합을 비교할 때 사용할 수 있다.
투 포인터는 시작과 끝, 두 지점을 움직이며 구간의 값을 구하는데, 슬라이딩 윈도우와는 달리 구간의 넓이가 유동적이라는 차이가 있다.
https://butter-shower.tistory.com/226

[Algorithm] 투포인터(Two Pointer) 알고리즘

https://ji-musclecode.tistory.com/37

슬라이딩 윈도우 알고리즘(Sliding Window) (feat. 투 포인트)

오늘 저녁은 위 블로그에서 투포인터와 슬라이딩 윈도우 문제를 풀어봐야겠다.