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

반복되는 문자가 없는 가장 긴 부분 문자열을 찾으십시오. 거의 모든 온라인 채점 시스템에서 등장하는 대표적인 슬라이딩 윈도 문제입니다. 🔤

모든 부분 문자열에서 중복을 확인하면 비용이 약 O(n^2) 이상 듭니다. 긴 문자열에서는 너무 느리므로 더 똑똑한 탐색이 필요합니다.

항상 서로 다른 문자만 포함하는 윈도를 유지합니다. 오른쪽으로 확장하다가 반복 문자가 나타나면 그 문자가 사라질 때까지 왼쪽에서 줄입니다.

각 문자의 마지막 인덱스를 사전에 저장합니다. 이렇게 하면 탐색 중 반복 문자가 마지막으로 나타난 위치를 즉시 알 수 있습니다.

문자열을 오른쪽으로 반복하며 각 단계에서 인덱스와 해당 위치의 문자를 함께 읽습니다. 이렇게 윈도를 한 번에 한 위치씩 앞으로 이동합니다.

해당 문자가 현재 윈도 안에서 이미 나타났다면 왼쪽을 그 문자의 마지막 위치 바로 다음으로 이동합니다. 한 번의 이동으로 중복을 제거할 수 있습니다.

이 문자의 새 위치를 기록하면 왼쪽부터 오른쪽까지의 윈도에 중복이 없어집니다. 길이는 오른쪽에서 왼쪽을 뺀 값에 1을 더한 값입니다.

last[ch] >= left 검사는 필수입니다. 이 검사가 없으면 윈도 밖에 있는 오래된 위치 때문에 왼쪽이 잘못해서 뒤로 이동하게 됩니다.

각 문자를 한 번씩만 방문하고 왼쪽은 앞으로만 이동하므로 탐색은 O(n)입니다. 사전은 서로 다른 문자들을 저장할 공간을 사용합니다.

빈 문자열의 답은 0이고, 같은 문자가 하나만 반복되는 문자열의 답은 1입니다. 제출하기 전에 두 경우를 모두 확인하여 뜻밖의 WA를 피하십시오.

마지막으로 본 위치를 저장하는 맵과 왼쪽 포인터를 건너뛰는 방식은 중복 없음을 다루는 여러 문제로 일반화할 수 있습니다. 예를 들어 반복이 최대 한 번인 윈도에 적용할 수 있습니다.

가장 긴 중복 없는 부분 문자열을 찾기 위해 탐색하면서 각 문자의 마지막 인덱스를 추적합니다.

서로 다른 문자로 이루어진 윈도를 이동하고, 각 문자의 마지막 위치를 저장한 다음 반복 문자를 지나 왼쪽을 건너뛰십시오. 이 고전적인 문제를 O(n)에 해결할 수 있습니다. ✅