단일 고유 문자로 구성된 하위 문자열 수를 계산합니다.

이 기사에서는 주어진 문자열에서 단일 개별 문자로 구성된 하위 문자열의 수를 계산하는 문제에 대해 논의합니다. 우리는 이 문제를 해결하기 위한 효율적인 알고리즘을 탐색하고 이를 구현하기 위한 C++ 코드를 제공할 것입니다.

문제 설명

문자열 S가 주어지면 작업은 단일 개별 문자로 구성된 하위 문자열의 수를 계산하는 것입니다.

예를 들어 입력 문자열이 "aaaaa"인 경우 단일 고유 문자로 구성된 15개의 하위 문자열이 있으므로 출력은 15가 되어야 합니다. 하위 문자열은 "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "aaa”입니다. , “아아아”, “아아아아”, “아아아아”, “아아아아”.

알고리즘

이 문제는 선형 시간 복잡도로 해결할 수 있습니다. 입력 문자열을 반복하고 현재 문자와 현재 하위 문자열의 길이를 추적할 수 있습니다. 새로운 문자를 만나거나 문자열의 끝에 도달할 때마다 현재 문자와 현재 하위 문자열의 길이로 형성될 수 있는 하위 문자열의 수를 계산할 수 있습니다.

이 문제를 해결하기 위한 단계별 알고리즘은 다음과 같습니다. -

• count 및 len을 1로 초기화합니다.

• 인덱스 1부터 n-1까지 문자열 S를 반복합니다.

• 현재 문자가 이전 문자와 동일하면 len이 1 증가합니다.

• 현재 문자가 이전 문자와 다를 경우 (len*(len+1))/2를 추가하여 개수를 계산하고 len을 1로 재설정합니다.

• 반품 횟수.

알고리즘을 이해하기 위해 문자열 "aaaaa"를 예로 들어보겠습니다. -

• count 및 len을 1로 초기화합니다.

• 인덱스 1부터 n-1까지 문자열을 반복합니다:

• 인덱스 1에서는 현재 문자가 이전 문자와 동일하므로 len이 1 증가합니다.

• 인덱스 2에서는 현재 문자가 이전 문자와 동일하므로 len이 1 증가합니다.

• 인덱스 3에서는 현재 문자가 이전 문자와 동일하므로 len이 1 증가합니다.

• 인덱스 4에서는 현재 문자가 이전 문자와 동일하므로 len이 1 증가합니다.

• 문자열의 끝에 도달했으므로 개수를 계산하려면 (len*(len+1))/2를 추가하세요. 개수 = 개수 + (5*(5+1))/2 = 15.

• 반품 횟수.

C++ 구현

위 알고리즘을 구현한 C++ 코드입니다 -

예

출력

결론

이 글에서는 주어진 문자열에서 단일 개별 문자로 구성된 하위 문자열의 수를 계산하는 문제에 대해 논의했습니다. 우리는 선형 시간 복잡도 문제를 해결하고 이를 C++로 구현하기 위한 효율적인 알고리즘을 제공합니다. 이 문제는 다른 기술을 사용하여 해결할 수도 있지만 위의 알고리즘은 다음을 제공합니다.

위 내용은 단일 고유 문자로 구성된 하위 문자열 수를 계산합니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!