← 8주차 · 투 포인터와 슬라이딩 윈도우
보통슬라이딩윈도우해시문자열

중복 없는 가장 긴 부분 문자열

문자열 s가 주어져요. 중복된 문자가 없는 가장 긴 연속 부분 문자열의 길이를 반환해요.

부분 문자열은 연속해야 해요. 순서를 건너뛴 부분 수열이 아니에요.

예시

예시 1
입력
s = "abcabcbb"
출력
3
설명
가장 긴 건 "abc"로 길이 3이에요.
예시 2
입력
s = "bbbbb"
출력
1
설명
"b" 하나가 최대예요.
예시 3
입력
s = "pwwkew"
출력
3
설명
"wke"가 답이에요. "pwke"는 연속하지 않아서 안 돼요.

제한 사항

  • 0 ≤ s.length ≤ 50,000
  • s는 영문자, 숫자, 기호, 공백으로 이루어져 있어요.
왼쪽 포인터와 오른쪽 포인터로 창을 유지해요. 오른쪽 문자가 창 안에 이미 있으면, 그 문자의 마지막 등장 위치 다음으로 왼쪽 포인터를 당겨요.
javascript
function lengthOfLongestSubstring(s) {
  const last = new Map();
  let left = 0;
  let best = 0;
  for (let right = 0; right < s.length; right++) {
    const ch = s[right];
    if (last.has(ch) && last.get(ch) >= left) {
      left = last.get(ch) + 1;
    }
    last.set(ch, right);
    best = Math.max(best, right - left + 1);
  }
  return best;
}
이전 문제가장 큰 연속 부분 수열의 합
다음 문제거스름돈 최소 동전 (배수 화폐)
에디터를 불러오고 있어요…
코드를 작성하고를 눌러 예시 테스트를 확인해 보세요.