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.

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: String algorithms

Data structures

Amortized analysis

Divide and conquer

Starter code: class Solution:
    def longestSubstring(self, s: str, k: int) -> int:
        

Solutions:
class Solution:

	def longestSubstring(self, s, k):
		for c in set(s):
			if s.count(c) < k:
				return max((self.longestSubstring(sp, k) for sp in s.split(c)))
		return len(s)


class Solution:

	def longestSubstring(self, s, k):
		characters = {}
		separators = set([])
		for char in s:
			char_count = characters.get(char, 0)
			characters[char] = char_count + 1
		for (char, count) in characters.items():
			if count < k:
				separators.add(char)
		for (i, char) in enumerate(s):
			if char in separators:
				return max(self.longestSubstring(s[0:i].rstrip(char), k), self.longestSubstring(s[i + 1:].lstrip(char), k))
		return len(s)


class Solution:

	def longestSubstring(self, s, k):
		if not s:
			return 0
		for c in set(s):
			if s.count(c) < k:
				return max((self.longestSubstring(t, k) for t in s.split(c)))
		return len(s)


class Solution:

	def longestSubstring(self, s, k):
		for i in set(s):
			if s.count(i) < k:
				return max((self.longestSubstring(t, k) for t in s.split(i)))
		return len(s)


class Solution:

	def longestSubstring(self, s, k):
		s_set = set(s)
		ans = -2147483647
		for c in s_set:
			if s.count(c) < k:
				return max([self.longestSubstring(_s, k) for _s in s.split(c)])
		return len(s)