[JS] Longest Substring Without Repeating Characters
2022. 7. 29. 16:40
🔒 문제 (LeetCode 3)
Given a string s, find the length of the longest substring without repeating characters.
Constraints:
- 0 <= s.length <= 5 * 104
- s consists of English letters, digits, symbols and spaces.
🌊 입출력
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.
🔑 해결
🌌 알고리즘 - sliding window
/**
* @param {string} s
* @return {number}
*/
function lengthOfLongestSubstring(s) {
const map = {}; // 각 문자의 가장 최근 index 저장
var left = 0; // 현재 substring의 시작 index
return s.split('').reduce((max, v, right) => {
// 현재 문자가 중복일 경우 substring의 시작 index 한 칸 이동
left = map[v] >= left ? map[v] + 1 : left;
map[v] = right; // 현재 문자를 substring의 끝으로 설정
return Math.max(max, right - left + 1); // substring의 최대 길이 반환
}, 0);
}
'코딩테스트 (JS) > 투포인터' 카테고리의 다른 글
[JS] Remove Duplicates from Sorted List II (0) | 2022.08.06 |
---|---|
[JS] Permutation in String (0) | 2022.07.29 |
[JS] Remove Nth Node From End of List (0) | 2022.07.29 |
[JS] Middle of the Linked List (0) | 2022.07.29 |
[JS] Reverse Words in a String III (0) | 2022.07.29 |