[leetcode] Longest Substring Without Repeating Characters

리트코드 문제: Longest Substring Without Repeating Characters

이 문제는 주어진 문자열에서 중복된 문자가 없는 가장 긴 부분 문자열을 찾는 문제입니다. 예를 들어, 문자열 "abcabcbb"가 주어졌다면 "abc"가 가장 긴 부분 문자열로, 답은 3입니다.

---

문제 분석

주어진 문자열에서 중복되지 않은 문자가 포함된 가장 긴 부분 문자열을 찾는 것이 목표입니다. 즉, 중복 문자가 나타나면 이전에 찾았던 부분 문자열을 중단하고, 중복이 없도록 시작 위치를 다시 조정해야 합니다.

---

풀이 접근

이 문제는 슬라이딩 윈도우와 같은 방식으로 해결할 수 있습니다. 슬라이딩 윈도우는 문자열에서 특정 범위를 탐색하면서 중복된 문자를 만나면 그 범위를 조정하는 방식입니다.

1. 문자열을 탐색하면서 중복 체크
   각 문자를 탐색하면서 그 문자가 이미 포함된 부분 문자열(result)에 있는지 확인합니다. 중복된 문자가 있다면 그 문자가 처음 등장한 위치 뒤부터 다시 시작해 새로운 부분 문자열을 만듭니다.
2. 최대 길이 갱신
   새로운 부분 문자열을 만들 때마다 그 길이를 체크하고, 가장 긴 부분 문자열의 길이를 answer로 저장합니다.

---

코드 설명

var lengthOfLongestSubstring = function (s) {
    let answer = 0;  // 가장 긴 부분 문자열의 길이 저장
    let result = []; // 현재 중복되지 않은 문자를 저장할 배열
  
    for (let i = 0; i < s.length; i++) {
      const char = s[i];   // 현재 문자를 하나씩 탐색
      const idx = result.indexOf(char);  // 현재 문자가 이미 result에 있는지 확인
      
      if (idx >= 0) {  // 중복 문자가 있으면 그 문자 이후부터 새로운 부분 문자열 시작
        result = result.slice(idx + 1); // 중복 문자의 다음부터 잘라서 사용
      }
      
      result.push(char);  // 현재 문자를 부분 문자열에 추가
      answer = Math.max(answer, result.length); // 가장 긴 길이 갱신
    }
  
    return answer;
};

코드 동작 방식:

1. result 배열은 현재 중복되지 않은 문자를 임시로 저장하는 곳입니다.
2. 문자열을 처음부터 끝까지 순회하면서, 각 문자가 result 배열에 존재하는지 확인합니다.
3. 만약 중복 문자가 발견되면, 그 중복 문자의 위치까지 result를 잘라냅니다. 이는 중복된 문자를 제거하고 새로운 부분 문자열을 만들기 위한 과정입니다.
4. 중복되지 않는 문자가 추가될 때마다 answer에 현재 부분 문자열의 길이를 저장하며, 최종적으로 가장 긴 부분 문자열의 길이를 반환합니다.

---

시간 복잡도 분석

• 최악의 경우, 문자열의 각 문자를 한 번씩만 순회하므로 **O(n)**의 시간 복잡도를 가집니다.
• result.indexOf()가 매번 O(n)의 시간이 걸리지만, 실제로는 한 번씩만 문자가 제거되므로 효율적으로 동작합니다.

---

성능 결과

• 실행 시간: 72ms (90.70% 보다 빠름)
• 메모리 사용량: 57.49MB (14.71% 보다 적음)

---

이 코드는 직관적이면서도 간단하게 문제를 해결합니다. 만약 더 최적화된 방법을 원한다면, indexOf()를 해시맵으로 대체하여 검색 속도를 줄일 수 있습니다.