395. Longest Substring with At Least K Repeating Characters | LeetCode Solution

 395. Longest Substring with At Least K Repeating Characters | LeetCode Solution

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.

 

Constraints:

  • 1 <= s.length <= 104
  • s consists of only lowercase English letters.
  • 1 <= k <= 105

class Solution
{
public:
  int longestSubstring(string s, int k)
  {
    int n = s.length();
    unordered_map<char, int> mymap;
    for (char c : s)
      mymap[c]++;

    int mid = 0;
    while (mid < n && mymap[s[mid]] >= k)
      mid++;
    if (mid == n)
      return n;
    int left = longestSubstring(s.substr(0, mid), k);
    while (mid < n && mymap[s[mid]] < k)
      mid++;
    int right = longestSubstring(s.substr(mid), k);
    return max(left, right);
  }
};

Post a Comment

0 Comments