[LeetCode/Medium] 3. Longest Substring Without Repeating Characters

1. Input

1) String s

 

2. Output

1) s의 부분 문자열 중에서 같은 문자가 없는 가장 긴 부분 문자열의 길이를 반환

 

3. Constraint

1) 0 <= s.length <= 5 * 10^4

2) s는 영어 대소문자, 숫자, 기호, 공백 문자로 이루어져 있다.

 

4. Example

Input: s = "abcabcbb" -> Output: 3

Input: s = "bbbbb" -> Output: 1

Input: s = "pwwkew" -> Output: 3

 

5. Code

1) 첫 코드

import java.util.*;
class Solution {
    public int lengthOfLongestSubstring(String s) {
        int answer = 0;        
        for(int i=0 ; i<s.length() ; i++){
            List<Character> list = new ArrayList<Character>();
            int j = i;
            while(j<s.length() && !list.contains(s.charAt(j))){
                list.add(s.charAt(j++));
            }
            answer = Math.max(answer, list.size());
        }
        return answer;
    }
}

- 5%, 11%

 

2) HashSet을 이용한 코드

import java.util.*;
class Solution {
    public int lengthOfLongestSubstring(String s) {
        int answer = 0;        
        for(int i=0 ; i<s.length() ; i++){
            HashSet<Character> set = new HashSet<>();
            int j = i;
            while(j<s.length() && !set.contains(s.charAt(j))){
                set.add(s.charAt(j++));
            }
            answer = Math.max(answer, set.size());
        }
        return answer;
    }
}

- 13%, 16%