[Leetcode] 3. Longest Substring Without Repeating Characters

✨ 문제 URL

LeetCode 3. Longest Substring Without Repeating Characters

---

✨ 문제 설명

주어진 문자열 s에서 중복 문자가 없는 가장 긴 부분 문자열(substring)의 길이를 구하는 문제입니다.

• Substring: 문자열 내에서 연속된 문자들의 집합
  • Subsequence(부분 수열)과는 달리 연속성이 보장되어야 합니다.

📌 예시

• s = "abcabcbb" → 정답: 3 ("abc")
• s = "bbbbb" → 정답: 1 ("b")
• s = "pwwkew" → 정답: 3 ("wke")

---

💡 접근 방법: Sliding Window + HashMap

이 문제는 슬라이딩 윈도우(Sliding Window)와 해시맵(HashMap)을 활용해 효율적으로 풀 수 있습니다.

1. 윈도우(window) 관리
   • left와 right 두 포인터를 사용해 현재 윈도우를 표현합니다.
   • right는 문자열을 순회하며 새 문자를 탐색합니다.
   • 중복이 발생하면 left를 이동시켜 윈도우 범위를 조정합니다.
2. HashMap 활용
   • 각 문자가 마지막으로 등장한 인덱스를 저장합니다.
   • 중복 문자가 나오면, 해당 문자의 마지막 인덱스 + 1을 left로 갱신합니다.
3. 최대 길이 추적
   • 매번 (right - left + 1) 값을 계산하여 지금까지의 최대 길이와 비교합니다.

---

🖼️ 슬라이딩 윈도우 동작 시각화

s = "abcabcbb" 를 예시로 살펴보겠습니다.

Step	Right Index	Current Char	Left Index 이동	Window 문자열	maxLength
1	0	'a'	-	"a"	1
2	1	'b'	-	"ab"	2
3	2	'c'	-	"abc"	3
4	3	'a'	0 → 1	"bca"	3
5	4	'b'	1 → 2	"cab"	3
6	5	'c'	2 → 3	"abc"	3
7	6	'b'	3 → 5	"cb"	3
8	7	'b'	5 → 7	"b"	3

👉 최대 길이는 3

---

✅ 코드 풀이

import java.util.HashMap;

class Solution {
    public int lengthOfLongestSubstring(String s) {
        // 문자의 마지막 인덱스를 저장하는 해시맵
        HashMap<Character, Integer> charIndexMap = new HashMap<>();

        int maxLength = 0;
        int left = 0; // 윈도우의 왼쪽 포인터

        // 오른쪽 포인터로 문자열 탐색
        for (int right = 0; right < s.length(); right++) {
            char currentChar = s.charAt(right);

            // 중복 문자가 발견된 경우
            if (charIndexMap.containsKey(currentChar) && charIndexMap.get(currentChar) >= left) {
                left = charIndexMap.get(currentChar) + 1;
            }

            // 현재 문자의 인덱스를 갱신
            charIndexMap.put(currentChar, right);

            // 최대 길이 갱신
            maxLength = Math.max(maxLength, right - left + 1);
        }

        return maxLength;
    }
}

• 시간 복잡도: O(n) (문자열을 한 번만 순회)