LeetCode 3번: Longest Substring Without Repeating Characters Java Solution

1. Problem Definition & Analysis

제목 그대로 중복 문자가 존재하지 않는 부분 문자열의 최대 길이를 구하는 문제이다.

Naive Solution은 $0 \le i < j \le s.length()$인 모든 $(i, j)$에 대해 s.substring(i, j)을 구하고 문자 중복 여부를 확인하는 것일 테지만, 입력 조건을 보면 $0 \le s.length \le 5 \times 10^4$이다. 이 알고리즘의 시간 복잡도는 $O(N^2)$이기 때문에 timeout이 발생할 것이다.

그래서 시간 복잡도가 $O(N)$인 슬라이딩 윈도우(Sliding Window) 알고리즘을 활용할 것이다. 아이디어는 단순하다.

1. 다음 문자를 추가해도 중복이 발생하지 않으면 슬라이딩 윈도우의 크기를 늘린다.
2. 다음 문자를 추가했을 때 중복이 발생하면 슬라이딩 윈도우의 크기를 줄인다.

슬라이딩 윈도우가 좌에서 우로 늘어나든 우에서 좌로 늘어나든 상관없다. 나는 전자의 경우를 고려해 코드를 짰다.

2. Solution

class Solution {
    public int lengthOfLongestSubstring(String s) {
        boolean[] dup = new boolean[256];
        int maxLength = 0, i = 0, j = 0;
        while (j < s.length()) {
            if (!dup[s.charAt(j)]) {
                dup[s.charAt(j++)] = true;
                maxLength = Math.max(maxLength, j - i);
            } else {
                dup[s.charAt(i++)] = false;
            }
        }
        return maxLength;
    }
}

슬라이딩 윈도우가 축소하는 지점은 i, 확장하는 지점은 j이다. 핵심은 아래의 코드 블럭이다.

        while (j < s.length()) {
            if (!dup[s.charAt(j)]) {
                dup[s.charAt(j++)] = true;
                maxLength = Math.max(maxLength, j - i);
            } else {
                dup[s.charAt(i++)] = false;
            }
        }

1. j번째 문자가 중복되지 않는다면 슬라이딩 윈도우를 확장하고 최대 길이(maxLength)를 갱신한다.
2. j번째 문자가 중복된다면 슬라이딩 윈도우를 축소한다.