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는 앞으로 돌아가는 경우가 없어야 함
                // 만약 max로 비교하지않으면 
                // ex) "abba" 의 경우 start가 b 때문에 2가 되었다가 
                // 마지막 a로 인해 다시 첫번째 b인 1이 된다.
                start = Math.max(check.get(now) + 1, start);
            }

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

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

        return res;
    }
}