.png&blockId=5f7573ad-6867-4d59-999e-722aced04aeb)
Medium
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.
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
복사
Constraints:
•
0 <= s.length <= 5 *
•
s consists of English letters, digits, symbols and spaces.
My solution
반복된 문자 없이 가장 긴 부분문자열의 길이를 구하는 문제다.
1번 TC를 보면
Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
abc까지 부분문자열로 인정하고 반복된 a가 나와서 abca가 되면 fail이다.
찾아보면 가장 긴 부분 문자열은 여러개지만 길이는 3이다. 따라서 그중 가장 빨리 발견한 abc을 답으로 한다.
3번 TC에서
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.
substring과 subsequence를 구분하고 있다.
substring은 연속된 부분 문자열을 뜻하고, subsequence는 연속적이지 않은 부분 문자열이다.
strArr.forEach((c, i) => {
if (indices[c] !== undefined && indices[c] >= start) {
start = indices[c] + 1;
} else {
max = Math.max(max, i - start + 1);
}
indices[c] = i;
});
JavaScript
복사
부분문자열의 시작 위치 start보다 같거나 크면 start는 indices[c]+1로 업데이트된다.
즉, 중복된 문자가 나타났을 때 슬라이딩 윈도우의 첫 부분을 나타내는 start를 한칸 뒤로 업데이트한다.
존재하지 않는 문자가 들어온다면 else문으로 진입한다. 이때는 현재 방문한 인덱스 i부터 start의 차이를 구한다음 +1을 하면 부분문자열의 길이를 구할 수 있다. 이 부분 문자열의 길이가 기존의 max보다 큰지 확인해서 max값을 업데이트한다.
아래의 콘솔은 indices라는 해시맵의 출력이다. 사용한 문자가 추가되고 사용된 인덱스가 계속해서 업데이트된다.
console.log('현재 문자', c, '슬라이딩윈도우', indices, 'size', i - start + 1);
indices[c] = i;
JavaScript
복사
Code
/**
* @param {string} s
* @return {number}
*/
const lengthOfLongestSubstring = function (s) {
const strArr = s.split('');
const indices = {};
let max = 0;
let start = 0;
strArr.forEach((c, i) => {
if (indices[c] !== undefined && indices[c] >= start) {
start = indices[c] + 1;
} else {
max = Math.max(max, i - start + 1);
}
indices[c] = i;
});
return max;
};
test('TC1', () => {
expect(lengthOfLongestSubstring('abcabcbb')).toStrictEqual(3);
});
test('TC2', () => {
expect(lengthOfLongestSubstring('bbbbb')).toStrictEqual(1);
});
test('TC3', () => {
expect(lengthOfLongestSubstring('pwwkew')).toStrictEqual(3);
});
JavaScript
복사
