[LeatCode] Medium Longest Substring Without Repeating Characters (Java)

문제 링크

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

문제 설명

주어진 문자열 s에서 중복되지 않는 문자들로 이루어진 가장 긴 부분 문자열의 길이를 반환하는 문제입니다.

예제 1

입력

s = "abcabcbb"

출력

3

예제 2

입력

s = "bbbbb"

출력

1

예제 3

입력

s = "pwwkew"

출력

3

접근 방식

완전 탐색은 O(N^2)의 시간 복잡도로 모든 부분 문자열의 중복 검사를 통해 문제를 해결할 수 있지만, 문자열의 최대 길이가 5 * 10^4 로 주어져 있어, 비효율적인 풀이가 됩니다.

따라서, O(N)의 시간 복잡도로 문제를 해결할 수 있는 슬라이딩 윈도우(Two-Pointer) 방식을 사용했으며, 중복된 문자를 효율적으로 검사하기 위해 HashSet 자료구조를 활용하여 시간 복잡도를 최소화했습니다.

구현

class Solution {
    public int lengthOfLongestSubstring(String s) {

        int answer = 0; // 결과로 반환할 가장 긴 부분 문자열의 길이
        Set<Character> set = new HashSet<>(); // 현재 윈도우에 포함된 문자들을 저장할 Set

        int lt = 0; // 슬라이딩 윈도우의 왼쪽 포인터
        for (int rt = 0; rt < s.length(); rt++) { // 오른쪽 포인터를 문자열 끝까지 이동
            char c = s.charAt(rt); // 현재 오른쪽 포인터가 가리키는 문자
            if (!set.contains(c)) { // 중복된 문자가 아니라면
                set.add(c); // Set에 추가
                answer = Math.max(answer, set.size()); // 현재 부분 문자열의 길이를 갱신
                continue;
            }

            // 중복된 문자가 발견된 경우
            while (s.charAt(lt) != c) { // 중복 문자가 사라질 때까지 왼쪽 포인터 이동
                set.remove(s.charAt(lt)); // Set에서 제거
                lt++; // 왼쪽 포인터 이동
            }
            // 중복된 문자를 제거한 후에도 왼쪽 포인터를 한 칸 더 이동
            lt++;
        }

        return answer; // 최종 결과 반환
    }
}

풀이 과정

• Set을 사용하여 현재 윈도우 안에 있는 문자들을 저장합니다.
• 오른쪽 포인터(rt)를 문자열의 시작부터 끝까지 순회하며, 중복된 문자가 있는지 확인합니다.
  • 중복된 문자가 없다면 Set에 문자를 추가하고, 현재 윈도우 크기를 기반으로 최대 길이를 갱신합니다.
  • 중복된 문자가 발견되면, 왼쪽 포인터(lt)를 이동시켜 중복 문자를 제거합니다.