395. Longest Substring with At Least K Repeating Characters
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
frequency of each character in this substring >= k
Approach
Divide and conquer solution
1function longestSubstring(s: string, k: number): number {
2 const divide_conquer = (start: number, end: number): number => {
3 if(end - start + 1 < k) {
4 return 0;
5 }
6
7 const freq: Record<string, number> = {}
8 for(let i = start; i <= end; i++) {
9 freq[s[i]] = (freq[s[i]] || 0) + 1;
10 }
11
12 for(let mid = start; mid <= end; mid++) { // O(n)
13 if(freq[s[mid]] < k) {
14 const left = divide_conquer(start, mid - 1); // O(n)
15 const right = divide_conquer(mid + 1, end);
16 return Math.max(left, right)
17 }
18 }
19
20 return end - start + 1;
21 }
22
23 return divide_conquer(0, s.length - 1)
24}Sliding window solution
1function longestSubstring(s: string, k: number): number {
2 let maxLen = 0;
3
4 /**
5 unique_count dùng để đếm số từ trong english lowercase letter
6 unique_target dùng để đếm số chữ unique để check điều kiện, vd check 'a' thôi hoặc check 'b' thôi
7 điều kiện cuối qua mỗi từ thì
8 - unique_count === unique_target để đảm bảo số từ check là đúng số lượng
9 - unique_target === count_at_least_k đảm bảo được số lượng từ trong substring đúng với điều kiện
10
11 */
12
13 for (let unique_target = 1; unique_target <= 26; unique_target++) {
14 let start = 0;
15 let end = 0;
16
17 let unique_count = 0;
18 let count_at_least_k = 0;
19
20 let f: number[] = new Array(26).fill(0);
21
22 while (end < s.length) {
23 if (unique_count <= unique_target) {
24 // Mở rộng cửa sổ
25 let char_index = s.charCodeAt(end) - 'a'.charCodeAt(0);
26 if (f[char_index] === 0) unique_count++;
27 f[char_index]++;
28 if (f[char_index] === k) count_at_least_k++;
29 end++;
30 } else {
31 // Thu nhỏ cửa sổ
32 let char_index = s.charCodeAt(start) - 'a'.charCodeAt(0);
33 if (f[char_index] === k) count_at_least_k--;
34 f[char_index]--;
35 if (f[char_index] === 0) unique_count--;
36 start++;
37 }
38
39 if (unique_count === unique_target && unique_count === count_at_least_k) {
40 maxLen = Math.max(maxLen, end - start);
41 }
42 }
43 }
44
45 return maxLen;
46}
47