슬라이딩 윈도우 기술을 사용하여 반복 문자가 없는 가장 긴 부분 문자열

해결 단계를 세분화하고 각 단계가 어떻게 작동하는지 살펴보겠습니다

다음과 같은 입력을 받았다고 가정합니다.

우리는 우리가 발견한 문자를 저장하기 위한 빈 세트와 우리가 찾은 가장 긴 부분 문자열을 유지하기 위한 변수를 만들 것입니다.

이제 오른쪽이 가리키는 값이 세트에 존재하는지 확인해 보겠습니다. 존재하지 않는 경우 세트에 추가하고 오른쪽으로 한 단계 앞으로 이동합니다. 그 후, set의 크기를 longSubstr 변수에 저장된 값과 비교하여 가장 긴 부분 문자열을 업데이트하겠습니다.

오른쪽이 가리키는 값이 세트에 있는지 확인해 보겠습니다. 그렇지 않은 것을 확인하고 이를 세트에 추가하고 바로 1씩 증가시킵니다. 그런 다음 세트의 크기와 longSubstr의 값 사이의 최대값을 취합니다.

오른쪽이 가리키는 값이 집합에 있는지 확인합니다. 즉, c가 집합에 없음을 의미합니다. 그래서 이를 세트에 추가하고 1씩 증가시킨 후 최대 하위 문자열을 확인합니다.

이제 오른쪽이 가리키는 값인 a가 집합에 존재하는지 확인합니다. 그렇다면 세트에서 제거하고 왼쪽으로 한 단계 앞으로 이동합니다.

오른쪽이 가리키는 값은 b이고, 집합에 존재합니다.

따라서 왼쪽 포인터를 한 단계 앞으로 이동하고 세트에서 b를 제거합니다.

이제 b가 집합에 포함되어 있으므로 왼쪽이 가리키는 값을 제거하고 왼쪽으로 한 단계 앞으로 이동합니다.

오른쪽이 가리키는 값은 c이고, 집합에 존재합니다.
따라서 세트에서 제거하고 왼쪽으로 한 단계 앞으로 이동합니다.

17단계까지 동일한 기술을 계속 사용하면 다음을 얻을 수 있습니다.

자바스크립트 구현은 다음과 같습니다

function longestSubstring(s) {
  let left = 0
  let right = 0

  let maxSubstr = 0
  let set = new Set()

  while (right < s.length) {
    const currentChar = s[right]

    if (!set.has(currentChar)) {
      set.add(currentChar)
      right++
      maxSubstr = Math.max(maxSubstr, right - left) // Update max substring length
    } else {
      set.delete(s[left])
      left++
    }
  }

  return maxSubstr
}

let inputString = 'abcabcbb'
console.log(longestSubstring(inputString)) // Output: 3 ("abc")

위 내용은 슬라이딩 윈도우 기술을 사용하여 반복 문자가 없는 가장 긴 부분 문자열의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!