3. Longest Substring Without Repeating Characters

문제 설명

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.

처음 생각했을 때 정말 막막했던 문제였다.
전체를 다 확인하기에는 시간이 너무 많이 걸릴 것 같고, 그 외에는 어떻게 해결해야 할 지 접근하기 어려웠다.

'중복되지 않음', 이라는 키워드에 집중했고, Sliding window 기법으로 해결할 수 있을거라는 생각이 들었다.

해당 기법을 적용하니 문제를 해결했고, Early Return 구조를 생각해 2개 만들어두었다.

첫 번째는 string의 길이가 1 이하일 때, 길이를 반환하도록 해두었고
두 번째는 최대 길이가 저장될 때(중복이 발생했을 때) 해당 최대 길이가 해당 문자열에서 가질 수 있는 최대 길이인지 확인하고 일치한다면 바로 해당 길이를 반환하도록 해두었다.

function lengthOfLongestSubstring(s: string): number {
  // Early return 1
  if (s.length <= 1) {
    return s.length;
  }

  let max = 0;
  let [l, r] = [0, 0];
  let buffer = new Set([s[0]]);
  const usedCharacters = new Set([...s]);

  while (r < s.length - 1) {
    if (!buffer.has(s[r + 1])) {
      r++;
      buffer.add(s[r]);
    } else {
      if (buffer.size > max) {
        max = buffer.size;
        if (max === usedCharacters.size) {
          return max;
        }
      }
      buffer.delete(s[l]);
      if (l === r) {
        buffer.add(s[l + 1]);
        r++;
      }
      l++;
    }
  }
  if (buffer.size > max) {
    max = buffer.size;
  }
  return max;
}

그렇게, 나쁘지 않은 결과가 나왔다.
하지만 두 번째 early return을 해주려던 것 때문에 공간복잡도는 그렇게 좋지 않은 모습을 보여준다.

요즘 Web 개발할 일이 많아서 처음으로 python이 아닌 TypeScript로 문제를 풀어보았는데 많이 어색하지 않고 괜찮았던 것 같다. 학습하고 있는 언어가 있다면 해당 언어로 틈틈이 알고리즘 문제를 풀어보아야겠다.