[LeetCode] Longest Substring Without Repeating Characters

Longest Substring Without Repeating Characters - LeetCode

문자열 s가 주어졌을 때, 반복되는 character가 없는 가장 긴 부분문자열의 길이를 구하라

문제 이해하기

• 정답은 substring이어야 한다. subsequence는 substring이 아님

example 3 설명을 보면 알 수 있다.

Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

문제 해결하기 : 슬라이딩 윈도우 ( 투 포인터 )

• susbsequence가 아닌 substring이어야 한다고 했기 때문에 , 슬라이딩 윈도우로도 풀 수 있을 거라는 생각이 들었다.
• 가장 먼저 드는 생각은 역시, sliding window 다
  • start, end라는 두개의 포인터를 사용한다. string상의 index를 가리키는 포인터다
  • 이 문제의 경우 O(n)으로 문제를 풀 수 있어 진다.
  • start = end = 0 에서 부터 시작하여, end를 increment 시킨다.
    • 이미 등장했던 character를 가리키게 된 경우, 더이상 repeated character가 없을 때 까지 start를 움직인다.
    • 이미 등장했던 character를 가리키게 된 경우에만, max값을 update한다
  • 이미 등장했던 character를 가리키게 된 경우에만 max값을 update하다보면 , 이 경우를 지나치게 된다.

    abcbdcaeg
    012345678

    end가 index 3 이 될 때 repeated character가 등장한다.

    1. max를 : end(3)-start(0) = 3 으로 업데이트 한다.

    2. start를 2 로 움직인다. ( s.charAt(start) == s.charAt(cur즉 end) 일 때 까지 이동)

       • 움직이는 동안 start 위치에 있던 것들은 visit[s.charAt(start)] = false로 업데이트한다

    3. visit[s.charAt(end)] = true 로 업데이트한다.

       end가 index 5 이 될 때 repeated character가 등장한다.

    4. max를 : end(5)-start(2) = 3 으로 업데이트 한다.

    5. start를 5 로 움직인다.( s.charAt(start) == s.charAt(cur즉 end) 일 때 까지 이동)

       • 움직이는 동안 start 위치에 있던 것들은 visit[s.charAt(start)] = false로 업데이트한다

    6. visit[s.charAt(end)] = true 로 업데이트한다.
       그리고는 end는 ++ 를 하다보면 -> end는 9, start는 5인 상태에서 끝난다.
       하지만 repeated character가 등장할 때만 max를 업데이트 하도록 했기에
       실제, 이 string s의 접미사 [ 5 ... ] 가 longest substring임에도 max 업데이트되지 않음
       따라서 for문 이 끝난 이후, 다시 한번 max를 업데이트한다

class Solution {
    /*
    
    ascii는 1byte를 사용하여 나타낼 수 있는 문자들에 대한 것
    128bit 
    영문자, symbol, space를 나타낼 수 있음 
    
    */
    public boolean[] visit = new boolean[1000];
    
    public int lengthOfLongestSubstring(String s) {
            
        int ans = sliding(s);
        return ans;
    }
    
   
    public int sliding(String s){
        int start=0, end=0,len = s.length();
        int cur = 0;
        int max = 0; 
        // System.out.println(len);

        for(; end<len; end++){
            cur = s.charAt(end)-0;
            if(visit[cur]){
                // repeated character인 경우 
                // 1. 길이를 저장 
                max = Math.max(max,end-start);
                // System.out.println("start :"+start+", end : "+end+", max : "+max);
                // 2. window를 오른쪽으로 이동
                while(start<end){
                    visit[s.charAt(start)-0] = false;
                    if(s.charAt(start) == s.charAt(end)){                        
                        start++;
                        break;
                    }
                    start++;
                }
            }
            visit[cur] = true; 
        }
        // end가 끝까지 간 경우 -> max를 update하는 로직이 실행되지 않는다. 
				// 즉, 접미사인 부분수열이 가장 긴 경우, for문에서는 탐색되지 않는다. 
        // 따라서 마지막에 이렇게, end-start 가 max일 수도 있기 때문에 이를 확인해 준다
        max = Math.max(max,end-start);
        // System.out.println("start :"+start+", end : "+end+", max : "+max);

        
        return max; 
    }
}