- 35.5%

https://leetcode.com/problems/longest-substring-with-at-least-k-repeating-characters/description/

Find the length of the longest substring T of a given string (consists of lowercase letters only) such that every character in T appears no less than k times.

1 | Example 1: |

方法一：

我的代码实现：

1 | class Solution { |

16ms, 23.77%, October 17, 2016

https://discuss.leetcode.com/topic/57735/c-recursive-solution

C++ recursive solution

- in the first pass I record counts of every character in a hashmap
- in the second pass I locate the first character that appear less than k times in the string. this character is definitely not included in the result, and that separates the string into two parts.
- keep doing this recursively and the maximum of the left/right part is the answer.

1 | class Solution { |

https://discuss.leetcode.com/topic/57134/two-short-c-solutions-3ms-and-6ms

Two short C++ solutions (3ms and 6ms)

Sol1: a simple improvement on the naive quaratic solution. The idea is that if a locally longest substr is found, there’s no need to check substrs overlapping it.

Sol1 can run O(n) times in some cases, but worst case is O(n2). Anyway the C++ run time is 3ms.

1 | int longestSubstring(string s, int k) { |

Sol2: recursive: split the string into substrs by characters of occurrence less than k. Then recursively apply the problem to each substr.

Worst case of Sol2 is O(n), because there are at most 26 levels of recursions. The C++ impl. runs 6ms. I suspect this is because the current test cases does not cover enough cases in favor of this solution in run time.

1 | int longestSubstring(string s, int k) { |

方法二：

比较直接，但是超时

我的代码实现：

1 | class Solution { |

#### python

55ms, 71.53%, October 17, 2016

https://discuss.leetcode.com/topic/57092/4-lines-python

1 | class Solution(object): |

49ms, 80.41%, October 17, 2016

https://discuss.leetcode.com/topic/57092/4-lines-python

1 | class Solution(object): |

#### java

4ms, 73.89%, October 17, 2016

https://discuss.leetcode.com/topic/57372/java-3ms-divide-and-conquer-recursion-solution

1 | public class Solution { |