[LeetCode] 3. Longest Substring Without Repeating Characters (JAVA)

Question 3.

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

Example 1:

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Example 2:

Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

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.

Example 4:

Input: s = ""
Output: 0

 

Constraints:

• 0 <= s.length <= 5 * 104
• s consists of English letters, digits, symbols and spaces.

 

Solution)

해당 문제는,, substring의 굴레에 벗어나지 못해 어렵게 풀었던 문제이다.
돌아보니 해당 문제는 ()(()) 괄호 문제 처럼 같은 문자가 있는 경우는 삭제하고 없으면 추가함으로써 Set의 사이즈의 max값을 구하는 문제이다.

class Solution {
    public int lengthOfLongestSubstring(String s) {
        
       
        int max = 0;
        int index =0;
        
        Set<Character> set = new HashSet<>();
        
        for(int i = 0; i < s.length(); i++) {
            char curchar = s.charAt(i); // i번째의 Character값
            
            while(set.contains(curchar)){ // curchar값이 포함되어 있을 경ㄷ우
                set.remove(s.charAt(index++)); // 삭제
            }
            
            
            set.add(curchar); // 추가
            max = Math.max(set.size(),max);
        
        }
        
        return max;
    }
}

예를 들어 "abcabcbb"값이 주어진다고 하면
Set 값에는

for문 I Index의 값	Set<Character>	max
0 (a)	a	1
1 (b)	a, b	2
2 (c)	a, b, c	3
3 (a)	b, c ,a (index =0 (a) 값 삭제)	3
4 (b)	c, a, b (index =1 (b) 값 삭제)	3
5 (c)	a, b, c (index =2 (c) 값 삭제)	3
6 (b)	b, c, b (index =3 (a) 값 삭제)	3
7 (b)	b, c, b (index =4  (b) 값 삭제)	3

 

끝.