start와 end가 substring의 시작과 끝을 가리킨다. substring의 길이와 substring의 각 알파벳을 해쉬에 넣었을 때의 길이가 같은지를 확인하여 중복된 알파벳이 존재하는지 여부를 확인한다. 만약 중복된 알파벳이 있다면, end에 있는 알파벳과 같은 알파벳을 찾아 start를 증가시킨다. 처음으로 같은 알파벳을 찾았을 때, start를 다시 1 증가시켜서 중복이 없는 substring을 만들어낸다. substring의 모든 알파벳이 유니크하다면, 그 길이와 현재까지의 최대 길이를 비교하여 수정한다.
Time complexity: O(N)
Space complexity: O(K), K는 Set의 크기
/**
* @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;
};
이전 방법은 start와 end가 처음으로 다른 알파벳을 찾기 위해 start를 계속 증가시키므로, start와 end 합쳐서 최대 2N번 순회하게 된다. 대신에 알파벳의 인덱스를 Map에 저장해두면, 바로 start의 위치를 찾을 수 있다. [i, j] 중에서 Map에 있는 s[j]의 위치가 i보다 크거나 같으면, [i, Map.get(s[j])]는 건너뛰면 된다.
[Map.get(s[end]+1), end]
가 된다.end-start+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;
};