Leet code (Medium): 3. Longest Substring Without Repeating Characters (슬라이딩 윈도우) - JAVA

 

 

이 문제는 "슬라이딩 윈도우" 알고리즘이다.

 

가장 긴 중복하지 않는 구간을 구하는 문제이므로, 각 알파벳을 돌되 시작점을 알고있어야한다.

그리고 그 시작점은 업데이트가 될 때, 뒤로만 이동 할 수 있다. 앞으로 땡겨져선 안된다.

 

class Solution {
    public int lengthOfLongestSubstring(String s) {

        if (s.length() <= 1) {
            return s.length();
        }

        Map<Character, Integer> check = new HashMap<>();
        int start = 0;  // 시작 인덱스
        int res = 0;    // 최대 길이
        
        for (int i = 0; i < s.length(); i++) {
            char now = s.charAt(i);
            
            // 중복된 문자가 있을 경우
            if (check.containsKey(now)) {
                // start를 뒤로 미는데 이때 윈도우를 벗어난 문자를 check에서 삭제하지 않기때문에
                // start를 하나씩 ++ 하는 것이 아니라
                // 문자가 안겹치는 곳(겹치는 문자 바로 다음)으로 이동 시킬때
                // start 보다 앞에 있는 문자면 무시하도록 다음과 같이 함. max 사용.
                start = Math.max(check.get(now) + 1, start);
            }

            // 최대 길이 갱신
            res = Math.max(res, i - start + 1);

            // 현재 문자와 인덱스 저장
            check.put(now, i);
        }

        return res;
    }
}