반복되는 문자가 없는 가장 긴 부분 문자열로 Google 인터뷰 질문을 해결합니다.

질문: 문자열이 주어졌을 때 반복되는 문자가 없는 가장 긴 부분 문자열의 길이를 찾으십시오.

예: 입력 = "abcabcbb"출력 = 3, "abc"는 반복 문자가 없는 가장 긴 부분 문자열이기 때문입니다.

질문 자체에서 우리는 고유한 문자를 추적할 수 있는 일종의 데이터 구조가 필요하다고 말할 수 있습니다.

이것은 Set을 사용하는 길을 열어줍니다.

이제 문자열을 구문 분석하는 방법은 무엇입니까? 질문은 "하위 문자열"을 요구합니다.

질문에 관련된 하위 문자열이 필요한 경우 두 포인터 접근 방식으로 해결해 보십시오.

두 포인터 접근

1 > 이 접근 방식은 간단하고 직관적입니다. 이 질문에 대해 왼쪽과 오른쪽의 두 포인터를 유지합니다.
2 > 왼쪽과 오른쪽을 0으로 초기화합니다.
3 > 오른쪽 포인터를 1만큼 이동하고 해당 문자를 집합에 추가합니다.
4 > 문자가 세트에 이미 있는 경우 왼쪽 포인터의 문자를 제거하고 왼쪽 포인터를 1만큼 이동합니다.
5 > 오른쪽 포인터가 문자열 끝에 도달할 때까지 이 작업을 계속합니다.

코드는 정말 간단하고 직관적입니다.

var lengthOfLongestSubstring = function(s) {
    let left = 0;
    let right = 0;
    let max = 0;
    let set = new Set();
    while(right<s.length){
        if(set.has(s[right])){
            set.delete(s[left]);
            left++;
        }else{
            set.add(s[right]);
            right++;
            max = Math.max(max,set.size);
        }
    }
    return max;
};

그게 다야! 제 설명이 마음에 드셨으면 좋겠습니다 :)

숨은 패턴만 알면 면접 크래킹 쉽죠 :P

깃허브: https://github.com/AKHILP96/Data-Structures-and-Algorithms/blob/master/problems/longestSubstringwithUniqueCharacters.js