길이가 K인 각 하위 문자열에 고유한 문자만 포함되도록 문자를 삽입하여 문자열을 수정합니다.

문자열을 처리할 때 일반적인 작업은 문자열이 특정 조건을 충족하는지 확인하는 것입니다. 조건 중 하나는 문자열에서 길이가 K인 각 하위 문자열에 고유한 문자만 포함되도록 하는 것입니다. 이는 데이터 인코딩, 문자열 조작 및 암호화와 관련된 문제의 일반적인 요구 사항입니다.

문제 설명

저희가 해결하려는 문제는 다음과 같습니다. -

문자열 str과 정수 K가 주어지면 문자열에서 길이가 K인 각 하위 문자열에 고유한 문자만 포함되도록 문자를 삽입하여 문자열을 수정합니다.

추천 솔루션

더 큰 배열이나 문자열에서 연속된 하위 배열이나 하위 문자열의 속성을 효율적으로 확인하는 방법인 슬라이딩 윈도우 기법을 사용하여 이 문제를 해결할 수 있습니다.

이 알고리즘의 단계를 자세히 설명하겠습니다 -

• 빈 unordered_map(해시맵)을 초기화하여 현재 하위 문자열의 문자 빈도를 추적하세요.

• K 크기의 슬라이딩 창을 사용하여 문자열의 문자를 반복합니다.

• 해시맵에 이미 문자가 있는 경우 고유한 문자를 얻거나 슬라이딩 창 크기가 K가 될 때까지 새 문자를 삽입하세요.

• 슬라이딩 창을 한 문자 이동하고 문자열 끝에 도달할 때까지 과정을 반복하세요.

이 알고리즘의 시간 복잡도는 O(n)입니다. 여기서 n은 문자열의 길이입니다. 이는 문자열의 각 문자를 한 번만 반복하기 때문입니다.

Example

Example

위 알고리즘을 구현한 C++ 코드를 살펴보겠습니다-

출력

이 코드는 반복되는 문자가 나타나면 무작위로 영문 소문자를 삽입합니다.

테스트 케이스 예시

이 문제를 더 잘 이해하기 위해 예를 들어 보겠습니다.

문자열 str = "abcabc" 및 K = 3을 고려하세요.

코드를 실행한 후 abcxyzabc와 유사한 결과를 얻을 수 있습니다. 세 문자 하위 문자열은 abc, bcx, cxy, xyz, yza, zab, abc이며 모두 고유한 문자를 포함합니다.

NOTE− 임의의 문자를 삽입하기 때문에 결과가 다를 수 있습니다.

결론

요약하자면, 이 알고리즘은 각 K 길이 하위 문자열이 고유한 문자를 갖도록 문자열을 수정하는 방법을 제공합니다. 이는 슬라이딩 윈도우 기술의 성능과 C++의 유연성을 활용하는 효율적인 솔루션입니다. 이 개념을 완전히 이해하려면 다양한 문자열과 K 값을 실험해 보시기 바랍니다.

위 내용은 길이가 K인 각 하위 문자열에 고유한 문자만 포함되도록 문자를 삽입하여 문자열을 수정합니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!