[오늘의 코테연습장] [LeetCode] 3. Longest Substring Without Repeating Characters

📑 문제

https://leetcode.com/problems/longest-substring-without-repeating-characters/?envType=study-plan-v2&envId=top-interview-150
반복되는 문자없이 가장 긴 subString의 길이를 return 하세요.

📑 접근 방식

처음에는 단순하게 모든 가능한 부분 문자열을 생성하고 검사하는 방식을 생각했습니다.
하지만 이 방법은 시간 복잡도가 높아서(시간 복잡도 O(n^2)) 실패했습니다.

그래서 슬라이딩 윈도우와 투 포인터 알고리즘을 활용하여 구현하였습니다.

left와 right를 이용하여 슬라이딩 윈도우를 구현하였습니다.
윈도우 내부에 중복 문자가 있으면 left 포인터를 오른쪽으로 한 칸씩 이동시키면서 해당 문자를 HashSet에서 제거하고, 중복 문자가 없으면 right 포인터를 오른쪽으로 한 칸씩 이동시키면서 새로운 문자를 HashSet에 추가하는 방식을 사용하였습니다.

그리고 매번 right 포인터가 이동할 때마다, 현재 슬라이딩 윈도우의 길이(즉, right - left + 1)와 지금까지 찾아낸 가장 긴 부분 문자열의 길이(maxLength)를 비교하여 더 큰 값을 저장하고, 더 큰 값을 최종적으로 return 하도록 구현햇습니다.

결과적으로, 위 코드는 시간 복잡도 O(n)으로 주어진 문제를 해결할 수 있었습니다.

📑 CODE

import java.util.HashSet;

class Solution {
public int lengthOfLongestSubstring(String s) {
int left = 0;
int right = 0;
HashSet<Character> subStringSet = new HashSet<>();
int maxLength = 0;

    while (right < s.length()) {
        if (subStringSet.contains(s.charAt(right))) { 
            subStringSet.remove(s.charAt(left));
            left++;
        } else {
            subStringSet.add(s.charAt(right));
            maxLength = Math.max(maxLength, right - left + 1);
            right++;
           
        }
    }

    return maxLength;
}
}