❄️ Solution 1 : Sliding Window

Intuition

start와 end가 substring의 시작과 끝을 가리킨다. substring의 길이와 substring의 각 알파벳을 해쉬에 넣었을 때의 길이가 같은지를 확인하여 중복된 알파벳이 존재하는지 여부를 확인한다. 만약 중복된 알파벳이 있다면, end에 있는 알파벳과 같은 알파벳을 찾아 start를 증가시킨다. 처음으로 같은 알파벳을 찾았을 때, start를 다시 1 증가시켜서 중복이 없는 substring을 만들어낸다. substring의 모든 알파벳이 유니크하다면, 그 길이와 현재까지의 최대 길이를 비교하여 수정한다.

Approach

• 0 <= start <= end < length이다.
• start <= end이고, end는 length 보다 작을 때 아래를 반복한다.
  • [start, end]인 substring을 만들어낸다.
  • substring의 길이가 substring의 알파벳의 Set과 같다면, substring의 길이를 최대 길이와 비교하여 수정한다. 그리고, end의 길이를 1 늘려서 다음 substring의 길이를 증가시킨다.
  • 만약 중복이 있다면, start와 end가 처음으로 같아질 때까지 start를 1 증가시킨다. 그리고 나서, start를 다시 1증가시켜 중복이 없는 substring을 만들도록 한다.

Complexity

• Time complexity: O(N)

• Space complexity: O(K), K는 Set의 크기

Code

/**
 * @param {string} s
 * @return {number}
 */
const lengthOfLongestSubstring = function (s) {
  let maxLen = 0;
  let start = 0;
  let end = 0;

  while (start <= end && end < s.length) {
    const substr = s.slice(start, end + 1);
    if (substr.length !== new Set([...substr]).size) {
      while (s[start] !== s[end]) {
        start += 1;
      }
      start += 1;
    } else {
      maxLen = Math.max(maxLen, substr.length);
      end += 1;
    }
  }

  return maxLen;
};

❄️ Solution 2: Sliding Window Optimized

Intuition

이전 방법은 start와 end가 처음으로 다른 알파벳을 찾기 위해 start를 계속 증가시키므로, start와 end 합쳐서 최대 2N번 순회하게 된다. 대신에 알파벳의 인덱스를 Map에 저장해두면, 바로 start의 위치를 찾을 수 있다. [i, j] 중에서 Map에 있는 s[j]의 위치가 i보다 크거나 같으면, [i, Map.get(s[j])]는 건너뛰면 된다.

Approach

• 0 <= start <= end < s.length
• start <= end && end s.length이면 다음을 반복한다.
  • s[end]가 Map에 있고, 그 index가 start보다 크거나 같으면, 현재 substring에서 중복된 알파벳이 있다는 것을 알 수 있다.
    • substring은 [Map.get(s[end]+1), end]가 된다.
    • 현재 s[start]의 index를 Map에 저장한다.
    • start를 Map에 있는 s[end]의 index보다 1 큰 값을 둔다.
  • end의 인덱스와 알파벳을 Map에 저장한다.
  • 현재 substring의 길이인 end-start+1이 현재 최대 길이보다 더 크다면, 업데이트한다.
  • end를 1 증가시킨다.

/**
 * @param {string} s
 * @return {number}
 */
const lengthOfLongestSubstring = function (s) {
  const alphaIndexMap = new Map();
  let maxLen = 0;
  let start = 0;
  let end = 0;

  while (start <= end && end < s.length) {
    if (alphaIndexMap.has(s[end]) && alphaIndexMap.get(s[end]) >= start) {
      start = alphaIndexMap.get(s[end]) + 1;
      alphaIndexMap.set(s[start], start);
    }
    alphaIndexMap.set(s[end], end);
    maxLen = Math.max(maxLen, end - start + 1);
    end += 1;
  }

  return maxLen;
};