해당 포스팅은 릿코드 3번 Longest Substring Without Repeating Characters 풀이를 다룬다. 문제 링크

코드는 Javascript로 작성했고 슬라이딩 윈도우로 풀이하였다.

문제

Given a string s, find the length of the longest substring without repeating characters.

문자열 s가 주어질 때, 반복되는 문자 없이 가장 긴 부분 문자열의 길이를 찾아라.

예제

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.

풀이

문제에서 부분 문자열을 구하라고 나와있으므로 슬라이딩 윈도우로 풀이해야 한다.

• 문자열 s를 loop돌리면서 문자를 해시에 넣고 원소의 개수인 maxLength를 업데이트한다.
• 이미 존재하는 문자일 시 해당 문자가 나올 때까지 원소들을 제거한다. 그 다음 해당 문자를 추가한다음 다시 maxLength를 업데이트 해준다.

전체 코드

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    let maxLength = 0,
    left = 0,
    chars = new Set();

    for (let i = 0; i < s.length; i++) {
        while (chars.has(s[i])) {
          chars.delete(s[left]);
          left++;
        }

        chars.add(s[i]);
        maxLength = Math.max(maxLength, chars.size);
    }

    return maxLength;
};