LeetCode - 3. Longest Substring Without Repeating Characters

Longest Substring Without Repeating Characters - LeetCode

 

---

문제

Given a string, find the length of the longest substring without repeating characters.

Example 1:

Input: "abcabcbb"

Output: 3

Explanation: The answer is "abc", with the length of 3.

 

Example 2:

Input: "bbbbb"

Output: 1

Explanation: The answer is "b", with the length of 1.

 

Example 3:

Input: "pwwkew"

Output: 3

Explanation: The answer is "wke", with the length of 3.

Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

---

문자열이 주어졌을 때 반복되는 문자 없이 가장 긴 substring의 길이를 찾아라!

 

처음에 문제를 잘못 이해하여 문자가 아닌 substring이 반복되지 않는 코드를 짜다가 시간을 허비했다..

 

중복되지 않는 값을 확인해야 한다고 생각했을 때 

 

O(1) 로 빠르고 값도 중복되지 않으니

 

Set 을 써야할 것 같았다.

 

import java.util.*;

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int answer = 0;
        int j = 0;

        Set<Character> set = new HashSet<>();
        
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            
            while(set.contains(c)) {
                set.remove(s.charAt(j));
                j++;
            }
            
            
            set.add(c);
            answer = Math.max(set.size(), answer);
        }
        
        return answer;
        
    }
}

 

[문제분석]

1. string을 리턴하는게 아니라 길이를 리턴한다.
   
   : func subString(String s) -> int
2. a-z 까지 26개의 알파벳 : 답이 제일 긴게 26 이다.
3. Brutal force solution
   
   func hasDup(String s){
       Set<char> set = new Set<>();
       for(char c : s){
           if set.contains s:
               return false;
           else
               add to set
       }
4. Time: O(n^3),  Space: O(n)
5. Sliding window 전략: i, j pointer set
   a b c a b c b
   i = a
   j = a
   sub="a"
   set={a}
   
   i = a
   j = b
   sub="ab"
   set{a,b}
   
   i = a
   j = c
   sub="abc"
   set{a,b,c}
   
   -----------------
   a로 겹쳤을 경우 i 를 increment 해서 조건이 성립되게 바꾼다.
   i = a -> b
   j = a
   sub = "bca"
   set{b,c,a}
   
   i = b -> c
   j = b
   sub = "cab"
   set{cab}
   
   --> O(n^2)

 

[참고영상]