###### tags: `Leetcode` `medium` `string` `divide and conquer` `python` `c++`

# 395. Longest Substring with At Least K Repeating Characters

## [題目連結:] https://leetcode.com/problems/longest-substring-with-at-least-k-repeating-characters/description/

## 題目:
Given a string ```s``` and an integer ```k```, return the length of the longest substring of ```s``` such that the frequency of each character in this substring is greater than or equal to ```k```.

**Example 1:**

Input: s = "aaabb", k = 3
Output: 3
Explanation: The longest substring is "aaa", as 'a' is repeated 3 times.

**Example 2:**

Input: s = "ababbc", k = 2
Output: 5
Explanation: The longest substring is "ababb", as 'a' is repeated 2 times and 'b' is repeated 3 times.

## 解題想法:
* 此題為給一個字符串s和一個正整數k:
* 求一個最大子字符串且每個字符必須至少出現k次。

* Divide and Conquer
* **判斷當前字符個數是否小於k**
* 若小於k，表示相當於遞迴求不包含此字符的子字串了

## Python:

class Solution(object):
    def longestSubstring(self, s, k):
        """
        :type s: str
        :type k: int
        :rtype: int
        """
        if len(s)<k:
            return 0
        for char in set(s): #不用考慮重複
            if s.count(char)<k: 
                return max(self.longestSubstring(sub,k) for sub in s.split(char))
        return len(s)

s = "ababbc"
k = 2
result= Solution()
ans=result.longestSubstring(s,k)
print(ans)

## C++:
* 因為c++沒有split
* 所以用substr分割，最後記得後半段也要遞迴判斷到

class Solution {
public:
    int longestSubstring(string s, int k) {
        int n=s.size(), index=0,res=0;
        bool SplitorNot=false;
        unordered_map<char, int> dic;
        for (char val: s){
            dic[val]+=1;
        }
        for (int i=0; i<n; i++){
            if (dic[s[i]]<k){
                //substr(start, step): 字串s從start起的step個字元
                res=max(res, longestSubstring(s.substr(index,i-index), k)); //前半段
                SplitorNot=true; // already split
                index=i+1;
            }
        }
        //若沒分割過: SplitorNot=false : 直接return s.size()即可
        //否則要判斷index~最後位置的子字串是否還有機會大於res
        return (!SplitorNot) ? n : max(res,longestSubstring(s.substr(index,n-1), k));
    }
};