Longest Substring with At Least K Repeating Characters

Longest Substring with At Least K Repeating Characters - LeetCode

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 <= 10^4
s consists of only lowercase English letters.
1 <= k <= 10^5

Solution

class Solution {
    func longestSubstring(_ s: String, _ k: Int) -> Int {
        var hash: [Character: Int] = [:] , ans = 0
        var ar = Array(s), splits = [Int]() , start = 0

        for item in ar { 
            hash[item] = hash[item, default: 0] + 1 
        }
        
        for i in 0..<ar.count { 
            if hash[ar[i]]! < k { 
                splits.append(i) 
            } 
        }

        if splits.count == 0 { return ar.count }

        for sp in splits {
            ans = max(ans, longestSubstring(String(Array(ar[start..<sp])), k) )
            start += 1
        }
        return max(ans, longestSubstring(String(Array(ar[start...])),k) )
    }
}

Tags: DSA LeetCode

Longest Substring with At Least K Repeating Characters - LeetCode : Swift

Solution