문제 설명
•
중복 문자가 없는 가장 긴 부분 문자열의 길이(lengthOfLongestSubstring)를 구하는 문제
예제 입력/출력
Example 1:
Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
Plain Text
복사
Example 2:
Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
Plain Text
복사
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.
Plain Text
복사
제약 조건
•
s.length
•
s는 영문자, 숫자, 기호 및 공백으로 구성됩니다.
문제 풀이
Sliding Window & Set -
•
자료구조
const set = new Set();
let left = 0;
let maxLength = 0;
JavaScript
복사
◦
Set: 현재 윈도우 내 중복 여부를 빠르게 확인하기 위한 해시 기반 자료구조
◦
left: Sliding Window 포인터
◦
maxLength: 반환해야 하는 값 (최대 길이)
•
알고리즘
for (let right = 0; right < s.length; right++) {
while (set.has(s[right])) {
set.delete(s[left]);
left++;
}
set.add(s[right]);
maxLength = Math.max(maxLength, right - left + 1);
}
JavaScript
복사
◦
left와 right 포인터로 슬라이딩 윈도우를 구성
◦
중복 문자가 나오면 left를 이동시켜 중복 제거
◦
중복이 없으면 set에 추가하고, right - left + 1을 이용해 최대 길이 갱신
풀이 코드
Sliding Window & Set - 6ms
var lengthOfLongestSubstring = function(s) {
const set = new Set();
let left = 0;
let maxLength = 0;
for (let right = 0; right < s.length; right++) {
while (set.has(s[right])) {
set.delete(s[left]);
left++;
}
set.add(s[right]);
maxLength = Math.max(maxLength, right - left + 1);
}
return maxLength;
};
JavaScript
복사
•
시간 복잡도: - 6ms
•
공간 복잡도: - 57.45MB