3. Longest Substring Without Repeating Characters

sliding window 문제

문자열에서 반복이 없는 가장 긴 부분 문자열을 찾는 문제.

 

abcabcbb -> abc

abcdab -> abcd

abcdb -> abcd

 

오른쪽으로 진행하면서 문자를 하나씩 확인한다.

만약 이번에 읽은 문자가 앞에 나왔던 문자와 중복된다면(set에 들어있다면), 현재 들고있는 부분문자열에서 중복된 문자와 그 앞의 모든 문자를 버려야 한다.

 

ex> abcd be 일 경우, b를 두번 만날 경우, 부분문자열에서 b와 그 앞의 문자(a)까지 모두 버려야 한다.

이를 위해서는 현재 윈도우 안에 어떤 문자가 있는지 들고있는 set이나 map이 필요하다.

 

그 앞의 문자를 모두 버려야 하므로, j를 0에서 시작하면서 하나씩 왼쪽으로 탐색하지 않고, size부터 시작해서 오른쪽으로 탐색하게끔 했다.

public int lengthOfLongestSubstring(String s) {
        char[] ch = s.toCharArray();
        Set<Character> set = new HashSet<>();
        int max = 0, now = 0;

        for (int i = 0; i < ch.length; i++) {
            if (!set.contains(ch[i])) {
                set.add(ch[i]);
                now++;
                if (max < now) {
                    max = now;
                }
            } else {
                int size = set.size();
                for (int j = size; j >= 1; j--) {
                    if (ch[i - j] == ch[i]) {
                        now = j;	// i-j번째부터 i까지의 부분문자열에는 중복이 없으므로, i - (i - j) = j
                        break;
                    } else {
                        set.remove(ch[i - j]);
                    }
                }
            }
        }
        return max;
    }