[LeetCode] 3. Longest Substring Without Repeating Characters — 슬라이딩 윈도우 개념 & 최적 풀이 (Java)

✔️ 오늘의 리트코드 공부 기록 – Longest Substring Without Repeating Characters (슬라이딩 윈도우 사고가 핵심이었다)

---

 

문제 요약 (Longest Substring Without Repeating Characters)

문자열에서 중복 문자가 없는 가장 긴 “연속 부분 문자열(substring)”의 길이를 구하는 문제

 

문제링크: https://leetcode.com/problems/longest-substring-without-repeating-characters/description/

---

🤔 처음 떠올린 접근 — 하지만 실패한 방법

 

문제를 처음 보자마자 자연스럽게 이렇게 생각했다.

 

“Set으로 중복만 막으면 되지 않을까?”
“right 포인터만 움직이면 되겠네?”

 

그래서 이렇게 구현했다 👇

class Solution {
  public int lengthOfLongestSubstring(String s) {
    Set<Character> set = new HashSet<>();
    
    int right = 0, maxLength = 0;
    while (right < s.length()) {
      char currentChar = s.charAt(right);
      if (!set.contains(currentChar)) {
        maxLength += 1;
        set.add(currentChar);
      }
      right++;
    }
    return maxLength;
  }
}

 

❌ 문제점

이 방식은 “중복을 만나도 window 를 정상적으로 줄이지 못함”

예: "pwwkew"

p → ok
w → ok
w (중복) → 처리 안함
k → ok
e → ok
w (중복) → 또 무시

 

하지만 실제 substring 기준으로 보면
✔ 유효하지 않은 길이를 계속 세고 있는 셈…

👉 즉, “윈도우 관리가 안 되는 Sliding Window”였다.

 

 즉,
✔ “문자만 저장하는 것”이 아니라
✔ “윈도우(window)를 유지 관리” 해야 한다는 걸 깨달음

---

😮올바른 해결 1 — Set + Sliding Window (기본형)

 

여기서 깨달은 핵심:

중복 문자를 만나면 단순히 넘기는 게 아니라
👉 “중복이 사라질 때까지 left 포인터를 이동해야 한다”

그래서 이렇게 수정 👇

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

 

 

📈 시간 복잡도

• O(n)
• 각각의 문자:
  right 로 1번, left 로 최대 1번 → 최대 2번만 방문

---

😮 최적화 해결 2 — HashMap + 점프 (Jumping Window)

 

Set 방식에서 이런 생각이 들었다.

“left 를 한 칸씩 움직이지 말고…
중복이 발생한 위치로 한 번에 점프하면 더 빠르지 않을까?”

 

그래서 중복 문자의 위치를 저장하기 위해 HashMap 사용 👇

class Solution {
  public int lengthOfLongestSubstring(String s) {
    Map<Character, Integer> map = new HashMap<>();
    
    int left = 0, maxLength = 0;
    for (int right = 0; right < s.length(); right++) {
      char currentChar = s.charAt(right);
      
      if (map.containsKey(currentChar) && map.get(currentChar) >= left) {
        left = map.get(currentChar) + 1;
      }
      
      map.put(currentChar, right);
      maxLength = Math.max(maxLength, right - left + 1);
    }
    return maxLength;
  }
}

 

✔️ 개선 포인트

• while loop 제거 → left 한 번에 점프
• map.get(c) >= left 조건으로 window 밖 값은 자동 무시

📈 시간복잡도

• O(n)

---

😮 최종 최적화 해결 3 — int 배열 (ASCII 제한일 때 최강)

 

ASCII 라면 더 빠른 방법 가능!

class Solution {
  public int lengthOfLongestSubstring(String s) {
    int[] index = new int[128];
    Arrays.fill(index, -1);
    
    int left = 0, maxLength = 0;
    
    for (int right = 0; right < s.length(); right++) {
      char c = s.charAt(right);
      
      if (index[c] != -1) {
        left = Math.max(left, index[c] + 1);
      }
      
      maxLength = Math.max(maxLength, right - left + 1);
      index[c] = right;
    }
    
    return maxLength;
  }
}

 

✔️ 장점

• HashMap → 배열로 대체
• 공간 복잡도가 O(1) (고정 128 크기)
• 훨씬 빠름

---

 

💡 핵심 아이디어

 

이 문제는 전형적인 Sliding Window + Two Pointer 패턴

핵심 개념

• “연속 substring”
• “중복 제거되도록 window 유지”
• left 는 상황에 따라 이동
• right 는 항상 앞으로만 이동

 

📈 알고리즘 비교

 

방식	시간	공간
Set + while	O(n)	O(min(n, charset))
Map Jumping	O(n)	O(min(n, charset))
int 배열	O(n)	O(1)

---

 

📝 이번 문제에서 얻은 깨달음

• “substring 문제 = Sliding Window 의 강력한 후보”
•  단순히 set으로 관리하는 것만으로는 부족하다
• 중복을 ‘발견’하는 것보다 👉 “중복 이후 window 를 어떻게 복구하는지”가 더 중요하다.
• 가능하면 Map / 배열로 jump 시켜 성능 개선
  • 기억할 패턴 : 중복이 발생하면 left를 이동시키며 window를 회복한다

 

 

Longest Substring Without Repeating Characters 는

“문자를 검사하는 문제”가 아니라
👉 “윈도우를 어떻게 유지 관리할지 이해하는 문제”