Longest Substring with At Least K Repeating Characters

Description

Find the length of the longest substring T of a given string (consists of lowercase letters only) such that every character in T appears no less than k times.

Example 1:

Input:
s = "aaabb", k = 3
Output:
3
The longest substring is "aaa", as 'a' is repeated 3 times.

Example 2:

Input:
s = "ababbc", k = 2
Output:
5
The longest substring is "ababb", as 'a' is repeated 2 times and 'b' is repeated 3 times.

Solution(javascript)

/*
 * @lc app=leetcode id=395 lang=javascript
 *
 * [395] Longest Substring with At Least K Repeating Characters
 */

// @lc code=start
// /** Sliding Window?
//  * O(N^2) TLE
//  * @param {string} s
//  * @param {number} k
//  * @return {number}
//  */
// const longestSubstring = function (s, k) {
//   let max = 0
//   for (let i = 0; i < s.length; i++) {
//     const need = {}
//     const map = {}
//     for (let j = i; j < s.length; j++) {
//       const nextC = s[j]
//       map[nextC] = (map[nextC] || 0) + 1
//       if (map[nextC] < k) {
//         need[nextC] = true
//       } else {
//         delete need[nextC]
//       }

//       if (Object.keys(need).length === 0) {
//         max = Math.max(max, j - i + 1)
//       }
//     }
//   }
//   return max
// }
/** Divide and conquer
 * @param {string} s
 * @param {number} k
 * @return {number}
 */
const longestSubstring = function (s, k) {
  let max = 0
  const aux = (str = '') => {
    if (str.length < k) {
      return 0
    }
    const map = {}
    for (const c of str) {
      map[c] = (map[c] || 0) + 1
    }
    const splitPoints = []
    for (let i = 0; i < str.length; i++) {
      const c = str[i]
      if (map[c] < k) {
        splitPoints.push(i)
      }
    }
    if (splitPoints.length === 0) {
      return str.length
    }
    splitPoints.push(str.length)
    let prev = 0
    splitPoints.forEach((point) => {
      max = Math.max(
        max,
        aux(str.slice(prev, point)),
      )
      prev = point + 1
    })
    return max
  }

  if (k <= 1) {
    return s.length
  }
  return aux(s)
}
// @lc code=end
// console.log(
//   longestSubstring(
//     // 'abbcba',
//     // 'abcba',
//     'aaabbbcdefcdefcde',
//     3,
//   ),
// )