반복 문자가 없는 가장 긴 부분 문자열 Leetcode 솔루션

난이도 중급
자주 묻는 질문 어도비 벽돌 아마존 Apple 블룸버그 게시물에서 Facebook 골드만 삭스 구글 인튜이트 Microsoft 신탁 페이팔 세일즈 포스 삼성 스포티 파이 동네 짱 VM웨어 Yahoo Yandex 주차 Zillow
해시맵 월마트 글로벌 테크조회수 45

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

문제 정책

또한 반복 문자가 없는 가장 긴 부분 문자열 LeetCode 솔루션 –  주어진 문자열 s를 나타냅니다. 우리는 찾을 필요가 가장 긴 부분 문자열 반복되는 문자 없이.

예:

Input:  s = "abcabcbb"
Output: 3

설명 :

  • 반복되는 문자가 없는 가장 긴 부분 문자열의 길이는 3입니다.
  • 문자열은 "abc"입니다.
Input:  s = "bbbbb"
Output: 1

설명 :

  • 모든 문자가 동일하므로 문자가 반복되지 않는 가장 긴 부분 문자열의 길이는 1입니다.

접근

아이디어 :

  1. 이 문제를 해결하기 위한 주요 아이디어는 해시 맵.
  2. 또한 무차별 대입 접근 방식을 사용하여 모든 하위 문자열을 고려하고 하위 문자열에 고유한 모든 문자가 포함되어 있는지 확인할 수 있습니다. 무차별 대입 접근 방식은 어레이의 최대 크기가 5 * 10^4이기 때문에 시간 제한 초과 판정을 제공합니다.
  3. 문자열의 문자를 다음과 같이 저장하는 해시맵을 유지하십시오. 키와 그 위치 가치로 유지하고 두 포인터 최대 하위 문자열을 정의합니다.
  4. 오른쪽 포인터를 이동하여 문자열을 스캔하고 해시맵을 업데이트합니다.
  5. 문자가 이미 해시맵에 있는 경우 왼쪽 포인터를 마지막으로 찾은 동일한 문자의 오른쪽으로 이동합니다. 두 포인터는 앞으로만 이동할 수 있습니다.
  6. 마지막으로 모든 문자가 다른 가장 긴 부분 문자열의 길이를 갖게 됩니다.

암호

반복 문자가 없는 가장 긴 부분 문자열 C++ 솔루션:

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        vector<int> occ(260,-2);
        int n = s.length(),ans = 0,j = 0;
        for(int i=0;i<n;i++){
            if(occ[s[i]]==-2){
                ans = max(ans,i-j+1);
            }
            else{
                while(j<=occ[s[i]]){
                    occ[s[j++]] = -2;
                }
            }
            occ[s[i]] = i;
        }
        return ans;
    }
};

반복 문자가 없는 가장 긴 부분 문자열 Java 솔루션:

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s.length()==0) return 0;
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        int max=0;
        for (int i=0, j=0; i<s.length(); ++i){
            if (map.containsKey(s.charAt(i))){
                j = Math.max(j,map.get(s.charAt(i))+1);
            }
            map.put(s.charAt(i),i);
            max = Math.max(max,i-j+1);
        }
        return max;
    }
}

복잡성 분석:

시간 복잡성

위 코드의 시간 복잡성은 의 위에) 문자의 발생을 추적하기에 충분한 크기의 벡터를 사용하거나 일정한 시간에 삽입 및 삭제를 허용하는 우수한 해시 함수(여기서 N = 입력 문자열의 크기)를 사용하는 경우.

공간 복잡성

위 코드의 공간 복잡성은 다음과 같습니다. O (M) 여기서 M = 해시맵의 크기입니다. 해시맵은 문자 항목을 저장합니다. 솔루션의 공간 복잡도는 전적으로 해시맵에 따라 다릅니다. 해시맵의 크기가 더 크면 공간 복잡도가 더 커질 것입니다.

균열 시스템 설계 인터뷰
Translate »