Leetcode Longest Substring with At Least K Repeating Characters problem solution YASH PAL, 31 July 2024 In this Leetcode Longest Substring with At Least K Repeating Characters problem solution, you have 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. Problem solution in Python. class Solution(object): def longestSubstring(self, s, k): if len(s) < k or k == 0: return 0 count = collections.defaultdict(int) for c in s: count[c] += 1 ranges = [] begin = end = 0 while end < len(s): if count[s[end]] < k: if end - begin >= k: ranges.append((begin, end)) begin = end + 1 end += 1 if end - begin >= k: ranges.append((begin, end)) if len(ranges) == 1 and end-begin == len(s): return end - begin maxLen = 0 for i, j in ranges: maxLen = max(maxLen, self.longestSubstring(s[i:j], k)) return maxLen Problem solution in Java. class Solution { public int longestSubstring(String s, int k) { return helper(s, k, 0, s.length() - 1); } private static int helper(String s, int k, int lo, int hi){ if (lo > hi) return 0; HashMap<Character, Integer> repeatNum = new HashMap<Character, Integer>(); for(int i = lo; i <= hi; i++){ int val = repeatNum.containsKey(s.charAt(i)) ? repeatNum.get(s.charAt(i)) + 1 : 1; repeatNum.put(s.charAt(i), val); } HashMap<Character, Integer> lessK = new HashMap<>(); for(char ch : repeatNum.keySet()){ if(repeatNum.get(ch) < k){ lessK.put(ch, repeatNum.get(ch)); } } for(char ch : lessK.keySet()){ int midLeft = s.indexOf(ch, lo); int midRight = midLeft; for(int i = midLeft + 1; i <= hi; i++){ if(s.charAt(i) == s.charAt(midLeft)) midRight++; else break; } return Math.max(helper(s, k, lo, midLeft - 1), helper(s, k, midRight + 1, hi)); } return hi - lo + 1; } } Problem solution in C++. class Solution { public: int longestSubstring(string s, int k) { vector<int> vocab(26,0); for(auto ch : s){ ++vocab[ch-'a']; } vector<int> cands; for(int i=0; i<s.size(); ++i){ if(vocab[s[i]-'a']<k){ cands.emplace_back(i); } } if(cands.empty()) return s.size(); cands.emplace_back(s.size()); int start = 0; int longest = 0; for(auto cand : cands){ if(cand-start>=k){ longest = max(longestSubstring(s.substr(start,cand-start),k),longest); } start = cand+1; } return longest; } }; Problem solution in C. void subroutine(char* s, int k, int first, int last, int* ans) { if ( first < 0 || first > last) { return; } int* temp = calloc(26, sizeof(int)); int flag = 0; for (int i = first; i < last + 1; i++) { temp[s[i] - 'a'] += 1; } while (first < last && temp[s[first] - 'a'] < k) { first++; } int begin = first, end = 0; ; for ( end = first; end <= last; end++) { if (temp[s[end] - 'a'] < k) { subroutine(s, k, begin, end - 1, ans); begin = end + 1; flag = 1; break; } } if (flag == 0 ) { if (*ans < last - first + 1) { *ans = last - first + 1; } return; } subroutine(s, k, begin, last, ans); } int longestSubstring(char * s, int k){ int len = strlen(s); int* ans = calloc(1,sizeof(int)); subroutine(s, k, 0, len-1, ans); return *ans; } coding problems