395. Longest Substring with At Least K Repeating Characters LeetCode Solution
In this guide, you will get 395. Longest Substring with At Least K Repeating Characters LeetCode Solution with the best time and space complexity. The solution to Longest Substring with At Least K Repeating Characters problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Longest Substring with At Least K Repeating Characters
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.
if no such substring exists, return 0.
Example 1:
Input: s = “aaabb”, k = 3
Output: 3
Explanation: The longest substring is “aaa”, as ‘a’ is repeated 3 times.
Example 2:
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 <= 104
s consists of only lowercase English letters.
1 <= k <= 105
Complexity Analysis
Time Complexity: O(26n) = O(n)
Space Complexity: O(26) = O(1)
395. Longest Substring with At Least K Repeating Characters LeetCode Solution in C++
class Solution {
public:
int longestSubstring(string s, int k) {
int ans = 0;
for (int n = 1; n <= 26; ++n)
ans = max(ans, longestSubstringWithNUniqueLetters(s, k, n));
return ans;
}
private:
int longestSubstringWithNUniqueLetters(const string& s, int k, int n) {
int res = 0;
int uniqueLetters = 0; // the number of unique letters
int lettersHavingKFreq = 0; // the number of letters having frequency >= k
vector<int> count(26);
for (int l = 0, r = 0; r < s.length(); ++r) {
if (++count[s[r] - 'a'] == 1)
++uniqueLetters;
if (count[s[r] - 'a'] == k)
++lettersHavingKFreq;
while (uniqueLetters > n) {
if (count[s[l] - 'a'] == k)
--lettersHavingKFreq;
if (--count[s[l] - 'a'] == 0)
--uniqueLetters;
++l;
}
// Since both the number of unique letters and the number of letters
// having frequency >= k are equal to n, this is a valid window.
if (lettersHavingKFreq == n) // Implicit: uniqueLetters == n
res = max(res, r - l + 1);
}
return res;
}
}; /* code provided by PROGIEZ */
395. Longest Substring with At Least K Repeating Characters LeetCode Solution in Java
class Solution {
public int longestSubstring(String s, int k) {
int ans = 0;
for (int n = 1; n <= 26; ++n)
ans = Math.max(ans, longestSubstringWithNUniqueLetters(s, k, n));
return ans;
}
private int longestSubstringWithNUniqueLetters(final String s, int k, int n) {
int res = 0;
int uniqueLetters = 0; // the number of unique letters
int lettersHavingKFreq = 0; // the number of letters having frequency >= k
int[] count = new int[26];
for (int l = 0, r = 0; r < s.length(); ++r) {
if (++count[s.charAt(r) - 'a'] == 1)
++uniqueLetters;
if (count[s.charAt(r) - 'a'] == k)
++lettersHavingKFreq;
while (uniqueLetters > n) {
if (count[s.charAt(l) - 'a'] == k)
--lettersHavingKFreq;
if (--count[s.charAt(l) - 'a'] == 0)
--uniqueLetters;
++l;
}
// Since both the number of unique letters and the number of letters
// having frequency >= k are equal to n, this is a valid window.
if (lettersHavingKFreq == n) // Implicit: uniqueLetters == n
res = Math.max(res, r - l + 1);
}
return res;
}
} // code provided by PROGIEZ
395. Longest Substring with At Least K Repeating Characters LeetCode Solution in Python
class Solution:
def longestSubstring(self, s: str, k: int) -> int:
def longestSubstringWithNUniqueLetters(n: int) -> int:
res = 0
uniqueLetters = 0 # the number of unique letters
lettersHavingKFreq = 0 # the number of letters having frequency >= k
count = collections.Counter()
l = 0
for r, c in enumerate(s):
count[c] += 1
if count[c] == 1:
uniqueLetters += 1
if count[c] == k:
lettersHavingKFreq += 1
while uniqueLetters > n:
if count[s[l]] == k:
lettersHavingKFreq -= 1
count[s[l]] -= 1
if count[s[l]] == 0:
uniqueLetters -= 1
l += 1
# Since both the number of unique letters and the number of letters
# having frequency >= k are equal to n, this is a valid window.
if lettersHavingKFreq == n: # Implicit: uniqueLetters == n
res = max(res, r - l + 1)
return res
return max(longestSubstringWithNUniqueLetters(n)
for n in range(1, 27)) # code by PROGIEZ
