Longest Substring With At Least K Repeating Characters Problem


Description

LeetCode Problem 395.

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:

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

Example 2:

1
2
3
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 <= 10^4
  • s consists of only lowercase English letters.
  • 1 <= k <= 10^5


Sample C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int longestSubstring(string s, int k) {
        if (s.size() == 0 || k > s.size())   
        	return 0;
        if (k == 0)  
        	return s.size();
        
        unordered_map<char,int> Map;
        for (int i = 0; i < s.size(); i++) {
            Map[s[i]]++;
        }
        
        int idx =0;
        while (idx <s.size() && Map[s[idx]] >= k) 
        	idx++;
        if (idx == s.size()) 
        	return s.size();
        
        int left = longestSubstring(s.substr(0, idx), k);
        int right = longestSubstring(s.substr(idx+1), k);
        
        return max(left, right);
    }
};




Related Posts

Find Duplicate Subtrees Problem

LeetCode 652. Given the rootof a binary tree, return all...

Delete And Earn Problem

LeetCode 740. You are given an integer array nums. You...

Degree Of An Array Problem

LeetCode 697. Given a non-empty array of non-negative integers nums,...

Custom Sort String Problem

LeetCode 791. You are given two strings order and s....

Basic Calculator IV Problem

LeetCode 770. Given an expression such as expression = “e...

Sort Characters By Frequency Problem

LeetCode 451. Given a string s, sort it in decreasing...