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.
How to Solve
Divide and Conquer is one of the popular strategies that work in 2 phases.
- Divide the problem into subproblems. (Divide Phase).
- Repeatedly solve each subproblem independently and combine the result to solve the original problem. (Conquer Phase).
We could apply this strategy by recursively splitting the string into substrings and combine the result to find the longest substring that satisfies the given condition.
Test Cases
Input:
(string) s = "aaabb"
(int) k = 3
Output:
(int) 3
Explanation:
The longest substring is "aaa", as 'a' is repeated 3 times.
Input:
(string) s = "ababbc"
(int) k = 2
Output:
(int) 5
Explanation:
The longest substring is "ababb", as 'a' is repeated 2 times, b 3 times.
Solution
class Solution {
public int longestSubstring(String s, int k) {
int[] chars = new int[26];
for(int i=0; i<s.length(); i++) {
chars[s.charAt(i) - 'a'] += 1;
}
boolean flag = true;
for(int i=0; i<26; i++) {
if (chars[i] < k && chars[i] > 0) flag = false;
}
if (flag) return s.length();
int pos = 0, max = 0, start = 0;
while(pos < s.length()) {
if (chars[s.charAt(pos) - 'a'] < k) {
max = Math.max(max, longestSubstring(s.substring(start, pos), k));
start = pos + 1;
}
pos++;
}
max = Math.max(max, longestSubstring(s.substring(start), k));
return max;
}
}