LeetCode 3. Longest Substring Without Repeating Characters

https://leetcode.com/problems/longest-substring-without-repeating-characters/description/

문제 파악

• 문자열 s가 주어진다.
• 중복 문자가 없는 substring 중에서 가장 긴 길이를 반환한다.
  
  

접근 방법

• 길이 최대 5만 : O(n²) 불가 (선형 시간 필요)
• 문자 종류는 제한적 : Set 사용 가능
• ‘연속구간’, ‘중복제거’, ‘최대길이’ 란 키워드들 : 슬라이딩 윈도우 패턴을 떠올려야한다.
  
  

윈도우란?

 [l ... r] = 현재 중복 없는 substring 구간

흐름

1. 오른쪽 포인터 end 확장(새로운 문자 s[end]를 윈도우에 포함시키려 시도한다)
2. 중복 검사 (중복이 사라질때까지 왼쪽 포인터 start 이동, s[start]를 Set에서 제거한다)
3. 현재 문자 추가
4. 최대 길이 갱신
   
   

• start와 end는 뒤로 가지 않는다
• 각 문자는
  • Set에 한 번 추가
  • Set에서 한 번 제거
• 총 연산 횟수는 O(n)
  
  

수도코드

start = 0
Set = empty

for end in 0..n-1:
    while Set contains s[end]:
        remove s[start] from Set
        start++

    add s[end] to Set
    update answer

 

코드 구현

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int start = 0;
        int maxLength = 0;
        Set<Character> set = new HashSet<>();

        for (int end = 0; end < s.length(); end++) {
            char c = s.charAt(end);

            // 중복이 없어질 때까지 윈도우 축소
            while (set.contains(c)) {
                set.remove(s.charAt(start));
                start++;
            }
            
            set.add(c); // 현재 문자 포함
            maxLength = Math.max(maxLength, end - start + 1); // 최대 길이 갱신
        }

        return maxLength;
    }
}

 

배우게 된 점

1. 슬라이딩 윈도우 기법을 사용해야만 하는 키워드들을 배웠다.

2. 슬라이딩 윈도우 기법을 사용할때 범용적으로 사용할 정석 패턴은 set 이 아닌 map 을 사용한 패턴이다.

 

Map 패턴으로 커버가능한 문제

• 중복 없는 substring
• k개 이하 / 이상 distinct
• anagram
• 최소 윈도우 substring
• 특정 문자를 몇 개 이상 포함
• 빈도 조건 문제 전부
  
  

반면 Set은 아래 케이스 밖에 커버 못한다.

• “있다 / 없다” 만 판단 가능
• 개수 조건, 빈도 조건 불가능

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> freq = new HashMap<>();
        int start = 0;
        int maxLength = 0;

        for (int end = 0; end < s.length(); end++) {
            char c = s.charAt(end);
            freq.put(c, freq.getOrDefault(c, 0) + 1);

            // 중복이 제거될 때까지 윈도우 축소
            while (freq.get(c) > 1) {
                char left = s.charAt(start);
                freq.put(left, freq.get(left) - 1);
                if (freq.get(left) == 0) {
                    freq.remove(left);
                }
                start++;
            }

            maxLength = Math.max(maxLength, end - start + 1);
        }

        return maxLength;
    }
}