所有字符至少出现K次的最大子字符串 | 系列 2
原文：https://www.geeksforgeeks.org/largest-substring-where-all-characters-appear-at-least-k-times-set-2/
给定字符串str和整数K，任务是找到最长子字符串S的长度，以使S中的每个字符出现至少K次。
示例：
输入：
str = "aabbba", K = 3输出：6
说明：
在子字符串
aabbba中，每个字符重复至少K次，其长度为 6。输入：
str = "ababacb", K = 3输出：0
说明：
没有每个字符重复至少
k次的子字符串。
朴素方法：我们在之前的文章中讨论了朴素方法。
方法：在本文中，我们将讨论使用分治技术和递归的方法。 步骤如下：
-
将给定字符串的每个字符的频率存储在大小为
26的频率数组中。 -
初始化两个变量，
start = 0，end是字符串str的长度。 -
从
start到end遍历字符串，并计算每个字符重复的次数并将其存储在数组中。 -
如果有任何字符重复的少于
K次，则将字符串分成两半。 如果i是我们发现str[i]重复少于K次的字符串的索引，则将字符串分为两半，从开始到i和i + 1到结束。 -
在上述步骤中递归调用两个半部分，即从开始到
i和i + 1到结束，然后重复步骤 2 和 3 并通过上述递归调用返回获得的两个值的最大值。 -
如果
start和end之间的所有字符至少重复K次，则答案是end - start。
下面是上述方法的实现：
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the longest substring
int longestSubstring(int start, int end,
string s, int k)
{
int left, right;
// Array for counting the number of
// times each character repeats
// count the number of times each
// character repeats from start to end
int count[26] = { 0 };
// Store the frequency from s[start...end]
for (int i = start; i < end; i++) {
count[s[i] - 'a'] += 1;
}
// Iterate from [start, end]
for (int i = start; i < end; i++) {
if (count[s[i] - 'a'] < k) {
// Recursive call for left subpart
left = longestSubstring(start,
i,
s,
k);
// Recursive call for right subpart
right = longestSubstring(i + 1,
end,
s,
k);
// Return maximum of left & right
return max(left, right);
}
}
// If all the characters are repeated
// at least k times
return end - start;
}
// Driver Code
int main()
{
// Given String str
string str = "aabbba";
int k = 3;
// Function Call
cout << longestSubstring(0, str.length(),
str, k)
<< endl;
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to find the longest subString
static int longestSubString(int start, int end,
String s, int k)
{
int left, right;
// Array for counting the number of
// times each character repeats
// count the number of times each
// character repeats from start to end
int count[] = new int[26];
// Store the frequency from s[start...end]
for(int i = start; i < end; i++)
{
count[s.charAt(i) - 'a'] += 1;
}
// Iterate from [start, end]
for(int i = start; i < end; i++)
{
if (count[s.charAt(i) - 'a'] < k)
{
// Recursive call for left subpart
left = longestSubString(start, i,
s, k);
// Recursive call for right subpart
right = longestSubString(i + 1, end,
s, k);
// Return maximum of left & right
return Math.max(left, right);
}
}
// If all the characters are repeated
// at least k times
return end - start;
}
// Driver Code
public static void main(String[] args)
{
// Given String str
String str = "aabbba";
int k = 3;
// Function Call
System.out.print(longestSubString(0, str.length(),
str, k) + "\n");
}
}
// This code is contributed by Amit Katiyar
Python3
# Python3 program for the above approach
# Function to find the longest substring
def longestSubString(start, end, s, k):
# List for counting the number of
# times each character repeats
# count the number of times each
# chracter repeats from start to end
count = [0 for i in range(26)]
# Store the frequency from s[start...end]
for i in range(start, end):
count[ord(s[i]) - ord('a')] += 1
# Iterate from [start, end]
for i in range(start, end):
if(count[ ord(s[i]) - ord('a')] < k):
# Recursive call for left subpart
left = longestSubString(start, i,
s, k)
# Recursive call for right subpart
right = longestSubString(i + 1, end,
s, k)
# Return maximum of left & right
return max(left, right)
# If all the characters are repeated
# at least k times
return end - start
# Driver Code
# Given String str
str = "aabbba"
k = 3
# Function call
print(longestSubString(0, len(str), str, k))
# This code is contributed by dadimadhav
C
// C# program for the above approach
using System;
class GFG{
// Function to find the longest subString
static int longestSubString(int start, int end,
string s, int k)
{
int left, right;
// Array for counting the number of
// times each character repeats
// count the number of times each
// character repeats from start to end
int []count = new int[26];
// Store the frequency from s[start...end]
for(int i = start; i < end; i++)
{
count[s[i] - 'a'] += 1;
}
// Iterate from [start, end]
for(int i = start; i < end; i++)
{
if (count[s[i] - 'a'] < k)
{
// Recursive call for left subpart
left = longestSubString(start, i,
s, k);
// Recursive call for right subpart
right = longestSubString(i + 1, end,
s, k);
// Return maximum of left & right
return Math.Max(left, right);
}
}
// If all the characters are repeated
// at least k times
return end - start;
}
// Driver Code
public static void Main(string[] args)
{
// Given String str
string str = "aabbba";
int k = 3;
// Function call
Console.Write(longestSubString(0, str.Length,
str, k) + "\n");
}
}
// This code is contributed by rutvik_56
输出：
6
时间复杂度：O(N * log2(N))。
版权属于：月萌API www.moonapi.com，转载请注明出处
