395. Longest Substring with At Least K Repeating Characters

Problem

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.

  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 <= 10^4

• s consists of only lowercase English letters.

• 1 <= k <= 10^5

Solution

/**
 * @param {string} s
 * @param {number} k
 * @return {number}
 */
var longestSubstring = function(s, k) {
    // Store the number of times each letter is encountered
    let mapOfLetters = {};
    for (let i = 0; i < s.length; i++) {
        mapOfLetters[s[i]] = mapOfLetters[s[i]] ? mapOfLetters[s[i]] + 1 : 1;
    }

    // If the entire string is made up of valid letters, return its full length
    if (Object.values(mapOfLetters).every((val) => val >= k)) return s.length;

    let longestSubstringFound = 0;
    let currentStart = 0;
    for (let i = 0; i < s.length; i++) {
        // If we've reached a breaking point (character that does not appear k times)
        if (mapOfLetters[s[i]] < k) {
            // Find the longest valid substring of the current string, and compare it with the longest found so far
            longestSubstringFound = Math.max(
                longestSubstring(s.substr(currentStart, i - currentStart), k),
                longestSubstringFound
            );

            // Move onto the next character in the string
            currentStart = i + 1;
        }
    }
    // Check if current substring would have been the longest if a breaking point had been encountered
    longestSubstringFound = Math.max(
        longestSubstring(s.substr(currentStart), k),
        longestSubstringFound
    );

    return longestSubstringFound > 1 ? longestSubstringFound : 0;
};

Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).