[LeetCode] 395. Longest Substring with At Least K Repeating Characters

😎풀이

1. s를 순회하며, 각 단어 빈도 확인
2. 빈도가 k 미만인 경우, 해당 단어 자체가 포함될 수 없으므로 기준 인덱스로 분리하여 좌측과 우측 중 가능한 더 긴 부분배열 탐색
3. 최대 길이의 부분배열의 길이 반환

function longestSubstring(s: string, k: number): number {
    if(s.length < k) return 0
    const freq = new Map()
    for(const char of s) {
        freq.set(char, (freq.get(char) ?? 0) + 1)
    }
    for(let i = 0; i < s.length; i++) {
        const char = s[i]
        if(freq.get(char) >= k) continue
        const left = longestSubstring(s.slice(0, i), k)
        const right = longestSubstring(s.slice(i + 1), k)
        return Math.max(left, right)
    }
    return s.length
};