[검지 Offer] 가장 긴 중복된 문자가 없는 하위 문자열(동적 기획 + 해시 테이블 업데이트 각 문자가 가장 최근에 나타난 하위 문자열)

카탈로그

제목

사고방식

동적 기획 + 해시 표

공간 절약

제목.
문자열에서 중복된 문자가 포함되지 않은 가장 긴 하위 문자열을 찾아서 가장 긴 문자열의 길이를 계산하십시오.

   1:
  : "abcabcbb"
  : 3 
  :               "abc"，       3。

   2:
  : "bbbbb"
  : 1
  :               "b"，       1。

   3:
  : "pwwkew"
  : 3
  :               "wke"，       3。
        ，              ，"pwke"       ，    。
 
  ：
s.length <= 40000

사고의 방향
동적 기획 + 해시 표

동적 계획: dp[i]를 설정하여 i를 끝으로 하는 중복 문자가 없는 하위 문자열의 길이를 나타낸다.

그러면 초기치 dp[0]=1, 최종 목적은 가장 긴 맥스(dp[0],..., dp[s.length()-1])를 구하는 것이다.

상태 전이 방정식: 최근 s[j]와 같은 문자의 출현 위치가 dp[j-1]에 포함되었는지 여부를 판단한다. (1) 존재하지 않거나 포함되지 않으면 직접 누적한다. dp[j]=dp[j-1]+1(즉 s[j]의 왼쪽 문자에 대해 s[j]와 같은 문자가 있으면 최근의 하표를 i로 설정하면 이 조건은 j-i>dp[j-1]에 해당한다. 존재하지 않으면 i=-1)(2) 그렇지 않으면 중복되는 것이 있으면 [j-45j](918)

이로써 우리는 모든 문자가 최근에 나타난 하표 위치를 기록해야 한다. 하시표

로 사용할 수 있다.
시간 복잡도 O (N), 공간 복잡도 O (N): 해시 테이블과 dp 그룹.

class Solution {
     
public:
    int lengthOfLongestSubstring(string s) {
     
        /*
            ： dp[i]   i                 。
             dp[0]=1，          max(dp[0], ... , dp[s.length()-1])。
              :
        （1）dp[j] = dp[j-1]+1（  s[j]     ，    s[j]     ，          i,          j-i>dp[j-1]。     i=-1 ）
        （2）        ， dp[j]=j-i
                               ，     
        */
        int size=s.length();
        if(size<=1){
     
            return size;
        }
        int anws = 0;
        vector<int> dp(size);
        unordered_map<char,int> unmap; //                 
        //  
        dp[0]=1;
        unmap[s[0]] = 0;
        //    
        for(int i=1;i<size;i++){
     
            //    ：    ，     
            if( unmap.find(s[i]) == unmap.end() ){
     
                dp[i] = dp[i-1] + 1;
            }else{
     
                //            dp[i-1]  
                int pos = unmap[s[i]];
                //   ：    ，    
                if( (i-pos) > dp[i-1] ){
      
                    dp[i] = dp[i-1] + 1;
                }else{
     //  ：             ，     
                    dp[i] = i - pos;
                }
            }
            //       
            unmap[s[i]] = i;
            //     
            if( anws < dp[i] )
                anws = dp[i];
        }
        return anws;
    }
};

공간 절약형
매번 dp는 지난번의 값만 사용하기 때문에 우리는 모든 dp를 저장할 필요가 없고 지난번의 값만 저장하면 공간을 절약할 수 있다.cur는 dp[i],pre는 dp[i-1]
시간 복잡도 O(N), 공간 복잡도 O(N): 해시표.

class Solution {
     
public:
    int lengthOfLongestSubstring(string s) {
     
        /*
            ： dp[i]   i                 。
             dp[0]=1，          max(dp[0], ... , dp[s.length()-1])。
              :
        （1）dp[j] = dp[j-1]+1（  s[j]     ，    s[j]     ，          i,          j-i>dp[j-1]。     i=-1 ）
        （2）        ， dp[j]=j-i
                               ，     
            dp        ，           dp，         ，    
        */
        int size=s.length();
        if(size<=1){
     
            return size;
        }
        int anws = 0;
        unordered_map<char,int> unmap; //                 
        //  
        int pre,cur;
        pre=1;
        unmap[s[0]] = 0;
        //    
        for(int i=1;i<size;i++){
     
            //    ：    ，     
            if( unmap.find(s[i]) == unmap.end() ){
     
                cur = pre + 1;
            }else{
     
                //            dp[i-1]  
                int pos = unmap[s[i]];
                //   ：    ，    
                if( (i-pos) > pre ){
      
                    cur = pre + 1;
                }else{
     //  ：             ，     
                    cur = i - pos;
                }
            }
            //       
            unmap[s[i]] = i;
            //     
            if( anws < cur )
                anws = cur;
            //  pre
            pre = cur;
        }
        return anws;
    }
};