[LeetCode] 3 Longest Substring Without Repeating Characters JavaScript
문제 링크
Longest Substring Without Repeating Characters - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
문제 유형
투 포인터 (Two Pointer)
문제 풀이
해당 문제는 중복되는 문자가 없는 가장 긴 서브 스트링을 찾아 반환하는 문제이다. 단순히 생각해보면 이중 for문으로 substring을 차례대로 만들고, 중복되는 문자 체크와 최대 길이를 저장하며 문제를 해결할 수 있을 것이다. 그러나 이는 O(n^2)의 시간복잡도를 가져 입력이 클수록 많은 시간이 걸린다. 해당 문제를 투 포인터로도 해결 가능하다.
아래 그림과 같은 입력이 주어졌다.
먼저, 배열의 처음부터 시작하는 포인터 2개와 서브 스트링의 최대 길이를 저장할 변수를 초기화한다. 그리고 배열 내의 알파벳의 위치를 저장할 테이블을 생성한다. 배열의 처음부터 끝까지 서브 스트링 내의 중복 알파벳을 체크 & 포인터 변경과 서브 스트링의 최대 길이를 계산하는 과정을 반복한다.
현재 서브 스트링 내에 중복을 체크한다. 중복은 없으므로 알파벳 테이블에 파란색 포인터가 가리키는 알파벳의 위치를 저장하고, 최대 길이를 갱신한다.
두 포인터 내에 중복된 알파벳이 존재하므로 start 포인터의 위치를 중복된 알파벳의 위치 다음으로 옮긴다. 현재 포인터가 가리키는 알파벳의 위치를 갱신한다. 그리고 현재 서브스트링과 최대 길이를 비교한다.
위와 같은 과정을 반복하면 서브 스트링의 최대 길이를 구할 수 있다.
배열의 길이를 n, 배열 내 알파벳의 개수를 m이라 할 때, 시간 복잡도와 공간 복잡도는 다음과 같다.
시간 복잡도 => O(n)
공간 복잡도 => O(m)
코드
var lengthOfLongestSubstring = function(s) {
const map = new Map();
let maxLength = 0;
for (let start = 0, end = 0; end < s.length; end++) {
const idx = map.get(s[end]);
if (idx >= start && idx <= end) start = idx + 1; // 알파벳 중복 체크
map.set(s[end], end); // 알파벳 테이블에 위치 정보 추가
if (maxLength < end - start + 1) maxLength = end - start + 1; // 최대 길이 갱신
}
return maxLength;
};