[LeetCode] 3. Longest Substring Without Repeating Characters

Description

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.

My Solution

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function (s) {
  const letterSet = new Set();
  let left = 0;
  let maxLength = 0;
  for (let right = 0; right < s.length; right++) {
    while (letterSet.has(s[right])) {
      letterSet.delete(s[left]);
      left++;
    }
    letterSet.add(s[right]);
    maxLength = Math.max(maxLength, right - left + 1);
  }
  return maxLength;
};

Time complexity

• Best case: O(n)
• Worst case: O(n)
• Average case: O(n)

Space complexity

• Best case: O(1)
• Worst case: O(n)
• Average case: O(min(m,n)) m: size of the character set

Feedback

Brute Force

function lengthOfLongestSubstring(s) {
  const n = s.length;
  let res = 0;
  for (let i = 0; i < n; i++) {
    for (let j = i; j < n; j++) {
      if (checkRepetition(s, i, j)) {
        res = Math.max(res, j - i + 1);
      }
    }
  }
  return res;
}

function checkRepetition(s, start, end) {
  const chars = new Set();
  for (let i = start; i <= end; i++) {
    const c = s.charAt(i);
    if (chars.has(c)) {
      return false;
    }
    chars.add(c);
  }
  return true;
}

Brute force time complexity

• Best case: O(n^2)
• Worst case: O(n^3)
• Average case: O(n^3)

Brute force space complexity

• Best case: O(n)
• Worst case: O(n)
• Average case: O(n)

Brute force보다 성능이 좋아진 이유

한 번 읽었던 아이템에 대한 정보를 letterSet 세트에 저장하였고, 모든 부분 문자열을 비교하지 않고 두 개의 포인터로 문자열을 순차적으로 읽으면서 읽은 부분까지의 최대 길이 부분 문자열의 정보만 저장했기 때문이다.
이러한 알고리즘 패러다임을 슬라이싱 윈도우(Slicing window)라고 한다.

슬라이싱 윈도우

슬라이싱 윈도우는 문자열 또는 배열에서 연속된 부분 문자열 또는 부분 배열을 처리하는 알고리즘 패러다임입니다. 슬라이싱 윈도우는 두 개의 포인터를 사용하여 연속된 요소의 부분집합을 선택하고, 이 부분집합을 처리한 후 포인터를 이동하여 다음 부분집합을 선택합니다.
고정된 크기의 윈도우를 사용하는 경우를 슬라이딩 윈도우(Sliding window)라고 합니다. 슬라이싱 윈도우는 연속된 요소의 부분집합 문제를 처리하는 데 사용되는 반면, 슬라이딩 윈도우 알고리즘은 연속된 구간에 대한 optimal solution을 찾는 데 사용됩니다.