문제
Given a string, find the length of the longest substring without repeating characters.
Example 1:
Input: "abcabcbb" Output: 3 Explanation: The answer is "abc", with the length of 3. Example 2:
Input: "bbbbb" Output: 1 Explanation: The answer is "b", with the length of 1. Example 3:
Input: "pwwkew" Output: 3 Explanation: The answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.
풀이
무식한 방법으로 풀기O(n2)
/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function(s) {
let result = 0;
for (let i = 0; i < s.length; i++) {
let count = 0;
const dup = new Set();
for (let j = i; j < s.length; j++) {
if (!dup.has(s[j])) {
dup.add(s[j]);
} else {
break;
}
count++;
}
result = Math.max(count, result);
}
return result;
};반복문으로 풀어보기 (O(n))
/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function(s) {
if (!s.length) return 0;
const map = new Map();
let i = 0,
j = 0,
result = 0;
while (j < s.length) {
if (!map.has(s[j])) {
map.set(s[j], j);
} else {
result = Math.max(result, j - i); // 최대길이 갱신
const pos = map.get(s[j]);
const final = pos + 1;
for (let k = i; k < final; k++) {
// map 갱신
map.delete(s[k]);
}
map.set(s[j], j); // 중복된 원소를 맵에 새롭게 추가
i = final; // 검사 시작 위치 변경
}
j++;
}
return Math.max(result, s.length - i);
};이렇게 풀 경우 O(n)으로 풀 수 있다.
결과
출처
https://leetcode.com/problems/longest-substring-without-repeating-characters