[leetcode - 3. Longest Substring Without Repeating Characters] java

문제 설명

1. 문자열이 주어진다.

2. 그 문자열에서 중복되지 않은 최대 서브문자열 길이를 구하면 된다.

 

풀이 과정 

1. 슬라이딩 윈도우 문제이다.

2. 왼 -> 오 로 가면서 문자들을 HashSet 에 저장하고 중복이 있다면 그 전까지 저장한 Set을 지운다.

3. 그리고 현재 위치까지의 값을 더하면 쉽게 구할 수 있다.

4. (2) 과정을 하기 위해서는 이전에 저장한 값들을 index 로 지우면 된다.

코드

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int ans = 0; // 최종 답
        int remover = 0; // hashSet 삭제를 위한 index
        HashSet<Character> hs = new HashSet<>(); // 현 위치까지의 문자들이 들어있는 hashSet

        for(int i=0; i<s.length(); i++) {
            char now = s.charAt(i); // 지금 문자가
            while(hs.contains(now)) { // 이전 HashSet 에 있었다고 한다면
                hs.remove(s.charAt(remover)); // 지금까지 문자열을 저장한 위치부터 중복 문자에 도달할 때 까지 다 지워준다.
                remover++;
            }
            hs.add(now); // 그리고 지금꺼 저장
            ans = Math.max(ans, hs.size());
        }

        return ans;
    }
}