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

난이도 중급
자주 묻는 질문 어도비 벽돌 얼레이션 아마존 Apple 블룸버그 게시물에서 ByteDance 시스코 DocuSign의 이베이 Expedia Facebook 골드만 삭스 구글 Microsoft 모건 스탠리 (Morgan Stanley) 신탁 페이팔 SAP SAP 연구소 ServiceNow 스포티 파이 동네 짱 VM웨어 월마트 연구소 Yahoo Yandex 주차 Zillow 조호 (Zoho)
해시 해싱 슬라이딩 윈도우 두 포인터조회수 117

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

반복 문자가 없는 가장 긴 부분 문자열 LeetCode 솔루션 – 주어진 , 우리는 문자를 반복하지 않고 가장 긴 부분 문자열의 길이를 찾아야합니다.

몇 가지 예를 살펴 보겠습니다.

pwwkew
3

설명 : 대답은 길이가 3 인“wke”입니다.

aav
2

설명 : 대답은 길이가 2 인“av”입니다.

접근 방식 -1 반복되는 문자가없는 가장 긴 부분 문자열 

브 루트 포스 

중복 문자에 대해 모든 하위 문자열이 하나인지 확인

  • 시간 복잡성
    • 형성 될 문자열 수 = n * (n + 1) / 2
    • 각 문자열을 확인하는 데 걸리는 시간 = O (n)
    • 따라서 시간 복잡도 = O (n ^ 3)
  • 공간 복잡성
    • 고유성 확인을위한 발생 문자 저장 = n
    • 따라서 공간 복잡성 = O (n)

접근 방식 -2 반복되는 문자가없는 가장 긴 부분 문자열 

슬라이딩 윈도우 

이제 우리는 최대 길이 부분 문자열 + 반복되는 문자가 없습니다.

  • 격언하자
  • 음 길이는 최대 0으로 초기화됩니다.
  • 우리는  ij-1 이미 확인되었습니다
  • j 번째 캐릭터를 만날 때마다
    • s [j]가 반복되지 않는 경우
      • 하위 문자열에 추가 할 수 있습니다.
      • 하위 문자열의 길이를 늘릴 수 있습니다.
      • j는 증가 할 수 있습니다.
      • s [j]를 HashSet에 기록 / 추가 할 수 있습니다.
    • s [j]가 반복되면
      • 우리는 문자를 제거합니다
      • 출발점, 즉 내가 변해야 해
      • 하위 문자열이 반복되지 않을 때까지이 작업을 수행합니다.

반복 문자가 없는 가장 긴 부분 문자열을 위한 Java 프로그램 LeetCode 솔루션

import java.util.*;
class Solution 
{
    public int lengthOfLongestSubstring(String s)
    {
        int max=0;
        HashSet<Character>hash=new HashSet<Character>();
        int i=0;
        int j=0;
        while(i<s.length() && j<s.length())
        {
            if(hash.contains(s.charAt(j)))
            {
                hash.remove(s.charAt(i));
                i=i+1;
            }
            else
            {
             hash.add(s.charAt(j));
             j=j+1;
             max=Math.max(j-i,max);   
            }
        }
        return max;
    }
}

class Main{
  public static void main(String[] args){
    int answer = (new Solution()).lengthOfLongestSubstring("pwwkew");
    System.out.print(answer);
  }
}
pwwkew
3

C ++ 프로그램

class Solution 
{
public:
    int maxs(int a,int b)
    {
        if(a>b)
            return a;
        else
            return b;
    }
public:
    int lengthOfLongestSubstring(string s) 
    {
    int max=0;
    set<char>hash;
    int i=0;
    int j=0;
    while(i<s.length() && j<s.length())
    {
      if(hash.count(s[j]))
      {
                hash.erase(s[i]);
                i=i+1;
      }
      else
     {
     hash.insert(s[j]);
     j=j+1;
     max=maxs(j-i,max);   
     }
    }
    return max;    
    }
};
pwwkew
3

복잡성 분석

시간 복잡성: 의 위에)

공간 복잡성: O (k) 여기서 k는 슬라이딩 윈도우의 크기입니다.

접근 방식 -3 반복되는 문자가없는 가장 긴 부분 문자열 

최적화 된 슬라이딩 윈도우 

위의 접근 방식에서는 반복되는 문자를 만날 때까지 계속 문자를 제거하고 문자열의 시작을 변경합니다.

해시 맵을 사용하여 repeating_character의 마지막 발생을 유지할 수 있으며 i (하위 문자열의 시작)를 해당 지점으로 이동하여 O (1) 연산을 수행 할 수 있습니다.

자바 프로그램

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

class Main{
  public static void main(String[] args){
    int answer = (new Solution()).lengthOfLongestSubstring("abcdefg");
    System.out.print(answer);
  }
}
abcdefg
7

C ++ 프로그램

class Solution 
{
public:
    int maxs(int a,int b)
    {
        if(a>b)
            return a;
        else
            return b;
    }
public:
    int lengthOfLongestSubstring(string s) 
    {
    int max=0;
    map<char,int>hash;
    int i=0;
    int j=0;
    while(j<s.length())
    {
    if(hash.count(s[j]))
    {
    i=maxs(hash[s[j]],i);
    }
    hash[s[j]]=j+1;
    max=maxs(j-i+1,max); 
    j=j+1;
    }
    return max;
    }
};
aabbccddee
2

복잡성 분석

시간 복잡도 : O (n)

공간 복잡도 : O (k) 여기서 k는 슬라이딩 윈도우의 크기입니다.

참조

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