문자가 하위 문자열과 동일하고 빈도 차이가 최대 K인 가장 긴 하위 시퀀스

이 문제에서는 연속된 문자를 포함하고 모든 문자의 빈도 차이가 K를 초과하지 않는 부분 수열의 최대 길이를 구합니다.

주어진 문자열의 가능한 모든 하위 시퀀스를 찾아 출력을 얻으려면 각 문자가 연속적으로 포함되어 있는지 그리고 최대 빈도 차이가 있는지 확인해야 합니다.

문제 설명- 알파벳 소문자를 포함하는 문자열 알파가 제공됩니다. 추가적으로 양의 정수 K가 주어졌습니다. 다음 규칙을 따르도록 주어진 문자열의 하위 시퀀스의 최대 길이를 찾아야 합니다.

• 특정 문자는 모두 연속되어야 합니다.

• 문자 빈도의 차이는 K보다 클 수 없습니다.

예

들어가세요

출력

설명 - "pppqrs" 하위 시퀀스를 사용할 수 있습니다. 최대 문자 빈도는 3이고 최소 문자 빈도는 1입니다. 따라서 차이는 2입니다. 그리고 모든 문자가 연속적으로 포함됩니다.

들어가세요

출력

설명 - "abbbc" 부분 수열을 사용할 수 있습니다.

들어가세요

출력

설명 - "nnnnnnn" 하위 시퀀스를 사용할 수 있습니다.

방법 1

이 방법에서는 재귀 함수를 사용하여 주어진 길이의 모든 하위 시퀀스를 찾습니다. 또한 하위 시퀀스에 모든 문자가 연속적으로 포함되어 있는지 확인하는 함수를 정의합니다. 최대 및 최소 주파수 차이를 계산하기 위해 맵 데이터 구조를 사용합니다.

알고리즘

1단계 - "f" 맵을 정의하여 문자의 빈도를 저장합니다.

2단계 - 시작이 임시 문자열의 길이와 같고 문자열 길이가 0보다 큰 경우 다음 단계를 따르세요.

3단계 - "minf" 및 "maxf" 변수를 초기화하여 최소 및 최대 주파수를 저장합니다.

4단계 - 지도를 지우고 지도에 있는 각 캐릭터의 빈도를 저장하세요.

5단계 - 지도 값을 반복하면서 최대 및 최소 빈도 값을 찾습니다.

6단계 - 최대 및 최소 주파수 차이가 K보다 작거나 같은 경우 문자열에 연속된 문자가 포함되어 있는지 확인하세요.

6.1단계 - checkForContinously() 함수에서 "pos" 맵을 정의하여 특정 문자의 마지막 위치를 저장합니다.

6.2단계 - 문자열을 반복합니다. 현재 캐릭터가 맵에 존재하고 캐릭터의 현재 위치와 마지막 위치의 차이가 1 미만인 경우 마지막 위치를 업데이트합니다. 그렇지 않으면 false를 반환합니다.

6.3단계 - 캐릭터가 존재하지 않으면 지도에 캐릭터를 추가하세요.

6.4단계 - 마지막으로 true를 반환합니다.

7단계 - 문자열에 연속 문자가 포함되어 있고 빈도 차이가 K보다 작은 경우 'maxi' 값이 현재 하위 시퀀스의 길이보다 작으면 'maxi' 값을 업데이트합니다. p>

8단계 - 현재 문자를 제외하고 재귀 호출을 합니다.

9단계 - 현재 문자를 임시 문자열 끝에 추가합니다. 또한 업데이트된 "tmp" 문자열을 사용하여 재귀 호출을 수행합니다.

예

출력

시간 복잡도 - O(N*2N), 여기서 O(N)은 연속 문자를 확인하고 O(2N)은 모든 하위 시퀀스를 찾습니다.

공간 복잡도 - 임시 하위 시퀀스를 저장하는 O(N)입니다.

우리는 주어진 문자열의 모든 하위 시퀀스를 찾기 위해 간단한 방법을 사용합니다. 그러나 이는 시간이 많이 소요됩니다. 큰 문자열 문제를 해결하기 위해 이 방법을 사용하지 않는 것이 좋습니다.

위 내용은 문자가 하위 문자열과 동일하고 빈도 차이가 최대 K인 가장 긴 하위 시퀀스의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!