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. Topics we are covering Toggle Problem solution in Python.Problem solution in Java.Problem solution in C++.Problem solution in C. 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 solutions