3. Longest Substring Without Repeating Characters

문제 링크: https://leetcode.com/problems/longest-substring-without-repeating-characters/?envType=study-plan-v2&envId=top-interview-150

문제

입력

• string s

출력

• 중복된 문자 없이 가장 긴 s의 substring

---

나의 풀이

처음 보자마자 생각했던 건, “바로 직전에 풀었던 209. Minimum Size Subarray Sum 이 문제의 풀이를 이용하면 되지 않을까?” 였다.

하지만 window 안의 substring에 현재 탐색하고 있는 문자가 존재하는 지 어떻게 검사하지? 가 관건이었다.

“window 안에 있는 요소들을 따로 변수를 할당해 관리하자” 가 핵심 아이디어였다.

구현 코드

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int left = 0;
        int answer = 1;
        Set<Character> set = new HashSet<>();
        if (s.length() == 0)
            return 0;
        set.add(s.charAt(0));
        for (int i = 1; i < s.length(); i++) {
            while (set.contains(s.charAt(i))) {
                set.remove(s.charAt(left++));
            }
            answer = Math.max(answer, i - left + 1);
            set.add(s.charAt(i));
        }
        return answer;
    }
}

• 먼저, window 안에 있는 요소를 저장할 HashSet을 선언
• i(window의 오른쪽 끝)를 증가
• 만약, window 안의 요소와 현재 탐색하고 있는 요소의 값이 같다면
  • 현재 window 안에 있는 중복 요소를 없앨 수 있을 때까지 왼쪽에서부터 window 사이즈를 감소
• 매번, answer의 값을 비교해 update 로직 통과
• window에 요소 추가

결과

Time: O(n)

Space: O(n)

---

사실 window 안에 있는 요소와 현재 보고 있는 요소가 중복인지 아닌지 확인하는 코드 실행을 어떻게 O(n)의 시간보다 짧게 가져갈 수 있을까에 대한 고민을 오래했었다.

하지만, HashSet은 탐색시간이 O(1), 상수시간이기 때문에 window로 이용하기 딱 좋았던 것 같다. 이렇게 for문을 돌 때마다 검사를 해야하는 로직이 필요하다면, Hash Table 을 이용한 자료구조를 먼저 생각해보아야겠다.

코딩 테스트 언어를 Java로 바꾼지 얼마 안됐기 때문에, Java의 여러 자료구조와 함수에 얼른 먼저 익숙해져야 한다.