Problem P06. [算法课分治] 找到 k 个最长重复字符串

注意是在该子字符串内每个字符的出现次数都不少于k。可以采用分治的方法，函数找一个不符合条件的字符，然后将字符串分成两个子字符串，就这样进行递归运算，每次找到符合条件的子字符串就判断一波长度，然后将最长的长度值存下来。

#include<iostream>
#include<bits/stdc++.h>
#include<cstdio>

using namespace std;

int k;
char s[10005];
int valmax = 0;

void longestSubstring(int left, int right)
{
    if (left >= right)
    {
        return;
    }
    int letter[30]={0};
    for (int i = left; i < right; i++)
    {
        letter[s[i]-'a']++;
    }
    for (int i = left; i < right; i++)
    {
        if (letter[s[i]-'a']<k)
        {
            longestSubstring(left, i);
            longestSubstring(i+1, right);
            return;
        }
    }
    valmax = max(valmax, right-left);
}

int main()
{
    scanf("%s %d", s, &k);
    longestSubstring(0, strlen(s));
    printf("%d", valmax);
    return 0;
}