Problem Explanation

The problem is asking to find the length of the longest substring which is consisting of a specific number of repeating characters. The repeating characters must not be less than given number k. If such a sequence exists return its length, else if it does not exist then return 0.

For instance consider the string "aaabb" and k = 3, we are asked to find the longest substring where every character is repeated at least 3 times, and in this case, it is "aaa". Another example would be "ababbc" and k = 2, the longest substring where every character is repeated at least 2 times is "ababb".

Approach

The problem is solved by using the sliding window approach. First, traverse the string using a for loop to find all unique characters (n).

In each iteration, use another for loop with two pointers initially pointing to the start of the string (l & r). The r pointer moves to the end until the number of unique characters in the window is greater than n. When this happens, the l pointer starts to move forward until the condition is satisfied again.

Keep track of the length of the substring that meets the condition (i.e., the number of characters appearing no less than k times is also n) and assign it to the ans variable after comparing it with the previous length. Repeat this process until the r pointer reaches the end of the string for all iterations. Finally, return the ans variable which now contains the length of the longest substring that meets the condition.

Throughout the process, keep count of the unique characters in the window and the count of characters that appear no less than k times in the window.

Python Solution

1
2python
3class Solution:
4    def longestSubstring(self, s: str, k: int) -> int:
5        ans = 0
6
7        for n in range(1, 27):
8            uniqueChars = 0 # Number of unique characters in window
9            noLessThanK = 0 # Count of characters >= k in window
10            count = [0] * 128
11
12            l = r = 0
13            while r < len(s):
14                if count[ord(s[r])] == 0:
15                    uniqueChars += 1
16                count[ord(s[r])] += 1
17                if count[ord(s[r])] == k:
18                    noLessThanK += 1
19
20                while uniqueChars > n:
21                    if count[ord(s[l])] == k:
22                        noLessThanK -= 1
23                    count[ord(s[l])] -= 1
24                    if count[ord(s[l])] == 0:
25                        uniqueChars -= 1
26                    l += 1
27                
28                if noLessThanK == n: # Unique chars also == n
29                    ans = max(ans, r - l + 1)
30                    
31                r += 1
32
33        return ans

Java Solution

1
2java
3class Solution {
4    public int longestSubstring(String s, int k) {
5        int ans = 0;
6
7        for (int n = 1; n <= 26; ++n)
8            ans = Math.max(ans, longestSubstringWithNUniqueCharacters(s, k, n));
9
10        return ans;
11    }
12
13    private int longestSubstringWithNUniqueCharacters(String s, int k, int n) {
14        int ans = 0;
15        int uniqueChars = 0;  // Number of unique chars in the window
16        int noLessThanK = 0;  // Count of characters >= k in the window
17        int[] count = new int[128];
18
19        for (int l = 0, r = 0; r < s.length(); ++r) {
20            if (count[s.charAt(r)] == 0)
21                uniqueChars++;
22            if (++count[s.charAt(r)] == k)
23                noLessThanK++;
24            while (uniqueChars > n) {
25                if (count[s.charAt(l)] == k)
26                    noLessThanK--;
27                if (--count[s.charAt(l)] == 0)
28                    uniqueChars--;
29                l++;
30            }
31            if (noLessThanK == n)  // Unique chars also == n
32                ans = Math.max(ans, r - l + 1);
33        }
34
35        return ans;
36    }
37}

C++ Solution

1
2c++
3class Solution {
4public:
5    int longestSubstring(string s, int k) {
6        int ans = 0;
7
8        for (int n = 1; n <= 26; ++n)
9            ans = max(ans, longestSubstringWithNUniqueCharacters(s, k, n));
10
11        return ans;
12    }
13
14private:
15    int longestSubstringWithNUniqueCharacters(string s, int k, int n) {
16        int ans = 0;
17        int uniqueChars = 0;  // Number of unique chars in the window
18        int noLessThanK = 0;  // Number of characters >= k in the window
19        vector<int> count(128);
20
21        for (int l = 0, r = 0; r < s.length(); ++r) {
22            if (count[s[r]] == 0)
23                uniqueChars++;
24            if (++count[s[r]] == k)
25                noLessThanK++;
26            while (uniqueChars > n) {
27                if (count[s[l]] == k)
28                    noLessThanK--;
29                if (--count[s[l]] == 0)
30                    uniqueChars--;
31                l++;
32            }
33            if (noLessThanK == n)  // Unique chars also == n
34                ans = max(ans, r - l + 1);
35        }
36
37        return ans;
38    }
39};

C# Solution

1
2csharp
3public class Solution {
4    public int LongestSubstring(string s, int k) {
5        int ans = 0;
6        
7        for (int n = 1; n <= 26; ++n)
8            ans = Math.Max(ans, LongestSubstringWithNUniqueCharacters(s, k, n));
9
10        return ans;
11    }
12
13    private int LongestSubstringWithNUniqueCharacters(string s, int k, int n) {
14        int ans = 0;
15        int uniqueChars = 0;  // Number of unique chars in the window
16        int noLessThanK = 0;  // Number of characters >= k in the window
17        int[] count = new int[128];
18
19        for (int l = 0, r = 0; r < s.Length; ++r) {
20            if (count[s[r]] == 0)
21                uniqueChars++;
22            if (++count[s[r]] == k)
23                noLessThanK++;
24            while (uniqueChars > n) {
25                if (count[s[l]] == k)
26                    noLessThanK--;
27                if (--count[s[l]] == 0)
28                    uniqueChars--;
29                l++;
30            }
31            if (noLessThanK == n)  // Unique chars also == n
32                ans = Math.Max(ans, r - l + 1);
33        }
34
35        return ans;
36    }
37}

JavaScript Solution

1
2javascript
3class Solution {
4    longestSubstring(s, k) {
5        let ans = 0;
6
7        for (let n = 1; n <= 26; ++n)
8            ans = Math.max(ans, this.longestSubstringWithNUniqueCharacters(s, k, n));
9
10        return ans;
11    }
12
13    longestSubstringWithNUniqueCharacters(s, k, n) {
14        let ans = 0;
15        let uniqueChars = 0; // Number of unique chars in the window
16        let noLessThanK = 0; // Number of characters >= k in the window
17        let count = Array(128).fill(0);
18
19        for (let l = 0, r = 0; r < s.length; ++r) {
20            if (count[s.charCodeAt(r)] == 0)
21                uniqueChars++;
22            if (++count[s.charCodeAt(r)] == k)
23                noLessThanK++;
24            while (uniqueChars > n) {
25                if (count[s.charCodeAt(l)] == k)
26                    noLessThanK--;
27                if (--count[s.charCodeAt(l)] == 0)
28                    uniqueChars--;
29                l++;
30            }
31            if (noLessThanK == n) // Unique chars also == n
32                ans = Math.max(ans, r - l + 1);
33        }
34
35        return ans;
36    }
37}
38
39let sol = new Solution();
40console.log(sol.longestSubstring("aaabb", 3)); //3
41console.log(sol.longestSubstring("ababc", 2)); //5

All of the solutions provided above utilize the Sliding Window approach, which works by maintaining a dynamic window of elements and making it slide over the data structure until it has visited all elements. The window size either increases or decreases based on the problem requirements.

For the problem of finding the longest substring with at least k repeating characters, the approach is to iterate over the string while adjusting the window size. During each iteration, unique characters and characters with a count of at least k are counted. If these two counts match, the current substring meets the requirement and can be considered as a candidate for the longest substring.

The Python solution makes use of ord() function that returns an integer representing the Unicode character, which is used as an index to store and track the count of each character in the string.

The Java solution follows a similar approach, but uses the charAt() method to access characters in the string. The C++ solution also adopts the same approach, but leverages a vector for character count, using ASCII values of characters as indices.

The C# solution is quite similar to the Java and C++ solutions. It uses an array to store character count and also takes advantage of ASCII values for indexing.

The JavaScript solution is also strikingly similar, using charCodeAt() method to get the Unicode of characters, then using it as an index to store the count of characters in an array. It also has an instance of the solution class for running test cases.

In all of these solutions, the algorithmic complexity would lie between O(n) and O(n^2), where n is the length of the string. This is because while there's a loop that iterates over the string, there's a nested while-loop that may or may not iterate over the whole string in worst-case scenarios, leading to quadratic time complexity. But in most cases, the while loop would not iterate over the whole string, tending towards a linear time complexity.