[LeetCode][JAVA] 3. Longest Substring Without Repeating Characters

💡 문제
3. Longest Substring Without Repeating Characters (https://leetcode.com/problems/longest-substring-without-repeating-characters/description/)
자세한 문제 설명과 입출력 예는 링크를 참고해주세요.

 

📝 선행 개념

• 슬라이딩 윈도우(Sliding Window): 두 포인터 left, right로 현재 고려하는 부분 문자열(윈도우)을 나타내며, 조건을 만족하도록 윈도우를 확장/축소한다.
• 중복 추적(최근 위치 인덱싱): Map<Character, Integer>에 각 문자의 가장 최근 등장 인덱스를 저장해, 중복이 감지되면 left를 건너뛰며 점프시킨다.
• 불변식: 매 반복에서 [left, right] 구간은 “중복 없는” 부분 문자열이어야 한다.

---

🤓 문제 풀이

주어진 문자열 s에서 중복 문자가 없는 가장 긴 부분 문자열의 길이를 구한다.
핵심은 오른쪽 포인터를 한 칸씩 이동하며 문자를 들여보내고, 중복이 발생하면 왼쪽 포인터를 중복 문자의 다음 칸으로 점프시키는 것이다. 이렇게 하면 각 문자는 왼쪽/오른쪽 포인터에 의해 최대 한 번씩만 넘어가므로 전체 시간은 O(n)이 된다.

 

🔨 문제 설명

• 입력: 문자열 s (0 <= s.length <= 5 * 10^4)
• 출력: 중복이 없는 가장 긴 부분 문자열의 길이

예)

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

---

🔨 접근 방법

1. last 맵에 문자 c의 최근 등장 인덱스를 기록한다.
2. 매 단계에서 right를 0부터 증가시키며 c = s.charAt(right)를 관찰:
   • 만약 c가 맵에 있고, last.get(c) >= left 라면 윈도우 안에서 중복이므로
     left = last.get(c) + 1 로 점프.
3. last.put(c, right)로 현재 위치 갱신.
4. 매 단계 maxLen = max(maxLen, right - left + 1)로 정답 갱신.

중요한 포인트: left는 절대 뒤로 가지 않음. 이전보다 더 왼쪽으로 이동시키면 윈도우 불변식(중복 없음)이 깨진다.

---

🔨 문제 풀이 과정

• 시작: left = 0, maxLen = 0, last = {}
• right를 증가시키며 각 문자를 본다.
• 중복이 아니면 윈도우 확장, 중복이 윈도우 내부에서 발견되면 left를 “중복 위치 + 1”로 점프.
• 모든 문자를 처리한 후의 maxLen이 정답.

예) s = "abba"

• r=0: 'a' (새 문자) → max=1
• r=1: 'b' (새 문자) → max=2
• r=2: 'b' (중복, last['b']=1 ≥ left=0) → left = 1+1=2, max=2
• r=3: 'a' (마지막 'a'는 0, 0 < left=2 → 윈도우 밖 중복) → max = max(2, 3-2+1=2)=2

---

🔨 구현코드

package leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * 3. Longest Substring Without Repeating Characters
 * - 슬라이딩 윈도우 + 최근 위치 인덱싱(HashMap)
 * - 시간복잡도 O(n), 공간복잡도 O(k)
 */
public class LeSolution01 {
    public int lengthOfLongestSubstring(String s) {
        // 엣지 케이스
        if (s == null || s.isEmpty()) {
            return 0;
        }
        if (s.length() == 1) {
            return 1; // 길이 1 문자열의 최장 길이는 1
        }

        Map<Character, Integer> last = new HashMap<>();
        int left = 0;
        int maxLen = 0;

        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);

            if (last.containsKey(c) && last.get(c) >= left) {
                // 윈도우 안에서 중복이므로 left를 '중복 다음 칸'으로 점프
                left = last.get(c) + 1;
            }

            last.put(c, right);
            maxLen = Math.max(maxLen, right - left + 1);
        }

        return maxLen;
    }
}

---

📚 풀이 보완

코드 설명 

• if (last.containsKey(c) && last.get(c) >= left):
  현재 윈도우 내부에서 중복일 때만 left를 점프해야 함 (윈도우 밖 중복은 무시).
• left = last.get(c) + 1:
  중복 문자를 윈도우에서 제거하기 위해 바로 다음 칸에서 새 윈도우 시작.
• maxLen = Math.max(maxLen, right - left + 1):
  매 스텝에서 가능한 최대 길이를 갱신.

🛠️ 버그 수정 포인트

• 원본 코드의 if (s == null || s.length() == 1) { return 0; }는 오류입니다.
  길이 1 문자열의 정답은 1이어야 하므로 return 1로 수정했습니다.
• s == null과 s.isEmpty() 분리 처리로 엣지 케이스 명확화.

---

📍 Plus+

대안 구현 아이디어

1. 고정 크기 배열 사용 (ASCII 한정)
   • 장점: HashMap보다 빠른 상수 시간.
   • 단점: ASCII 범위 가정. (일반 유니코드 전체는 별도 처리 필요)
2. int[] last = new int[128]; Arrays.fill(last, -1); int left = 0, maxLen = 0; for (int right = 0; right < s.length(); right++) { char c = s.charAt(right); if (last[c] >= left) left = last[c] + 1; last[c] = right; maxLen = Math.max(maxLen, right - left + 1); }
3. 문자셋이 아주 크면 HashMap 유지가 안전. (이 문제의 입력은 영문/숫자/기호/공백이라 Map/배열 모두 OK)

자주 하는 실수

• 중복이 윈도우 밖일 때도 left를 갱신해버리는 실수 → 길이를 과도하게 줄임.
• left를 단순히 last.get(c)+1로 바꾸지 않고 1칸씩 증가시키는 방식 → O(n^2)로 느려짐.
• 길이 1/빈 문자열 처리 누락.

 

시간 복잡도와 공간 복잡도 분석

 

• 시간 복잡도: O(n)
  • right 포인터가 0→n-1로 딱 한 번 전진.
  • left 포인터는 뒤로 가지 않음.
  • 각 문자는 많아야 2번(들어올 때/윈도우에서 밀려날 때) 관찰됨.
• 공간 복잡도: O(k)
  • k는 윈도우에 동시에 존재 가능한 서로 다른 문자 수.
  • 입력 문자셋이 제한적이면 상수에 가깝다.

요약

• 시간복잡도: O(n)
• 공간복잡도: O(k)
• 전략: 슬라이딩 윈도우 + 최근 인덱스 맵으로 중복 시 left 점프.
• 정당성: 윈도우 불변식(중복 없음)을 유지하며, 각 문자를 상수 시간에 처리.

 

---

풀이 참고 로직

 

• 중복 감지 조건: last.containsKey(c) && last.get(c) >= left
• 점프: left = last.get(c) + 1
• 정답 갱신: maxLen = Math.max(maxLen, right - left + 1)