LeetCode 3(Longest Substring Without Repeating Characters, java)

0. 문제

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

Longest Substring Without Repeating Characters - LeetCode

 

 

1. 문제 설명

- 문제에서 문자열(s)이 주어진다.

- 문자열을 탐색하여 중복 없이 구성된 내부 문자열 중 가장 긴 길이를 찾는 것이 핵심이다.

 

 

2. 문제 해설

a) 첫 번째 접근

- 우선 문자열을 탐색한다.

- 그러므로 반복문과 charAt() 메서드를 사용하여 각 문자에 접근할 것이다. 

 

 

b) 두 번째 접근

- 이 문제를 해결하기 위해서는 two pointers 방식을 사용할 예정이다. 

- 그 이유는 다음과 같다. 

 

- 예를 들어, abca라는 문자열이 있다고 해보자.

 

- 첫 번째 탐색을 수행한다. 

- 첫 번째 a를 시작점으로, 두 번째 a를 만날 때까지 탐색한다. 

- 첫 번째 탐색에서는 abc는 3의 길이를 갖는다.

 

- 두 번째 탐색을 수행한다.

- 두 번째 탐색의 시작점은 b가 되어야 한다.

- 두 번째 탐색에서 bca는 3의 길이를 갖는다. 

 

- 이 방식을 for문으로 구현한다면 이중 for문을 작성해야 하므로 탐색 효율이 좋지 않다.

- 그러므로 동일한 연산을 수행하지만 시간 복잡도가 더 효율적인 two pointer 방식을 사용한다.

 

 

c) 세 번째 접근

- 중복을 필터링하기 위해서 Set 자료구조를 사용한다.

- 이 문제의 핵심은 Set 자료구조를 운용하는 방식에 있다. 

- 중복된 문자를 만난 시점에서 가장 과거에 저장된 문자를 제거하는 것이다.

 

- 예를 들어, abca라는 문자열을 탐색한다고 해보자.

- c까지 탐색했을 때, Set에는 abc가 저장되어 있다.

- 그리고 중복된 문자(= 두 번째 a)를 만난 경우, b부터 탐색을 재개한다.

 

- 이처럼 중복된 문자를 만났을 때, 첫 번째 문자(= a)를 Set에서 제거한다.

- 그러면 Set에는 bc가 저장되어 있다.

- 즉, b부터 다시 탐색할 필요 없이 마치 b부터 탐색을 수행한 상태가 되는 것이다.

 

- 이처럼 Set에 가장 처음에 저장된 문자의 위치를 two pointers 중 하나에 기록한다.

 

- 다음 코드를 보면서 이해해보자. 

 

 

3. 정답 코드

class Solution {
    public int lengthOfLongestSubstring(String s) {
        
        int prev = 0;
        int idx = 0;
        int max = 0;
        Set<Character> set = new HashSet<>();
        
        while(idx < s.length()) {
            char curn = s.charAt(idx);
            if(!set.contains(curn)) {
                set.add(curn);
                idx++;
                max = Math.max(max, set.size());
            }
            else {
                set.remove(s.charAt(prev));
                prev++;
            }
        }
        return max;
    }
}