Hash Table
String
Divide and Conquer
Sliding Window
Description
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 <= 104
s
consists of only lowercase English letters.
1 <= k <= 105
Solutions
Solution 1
Python3 Java C++ Go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 class Solution :
def longestSubstring ( self , s : str , k : int ) -> int :
def dfs ( l , r ):
cnt = Counter ( s [ l : r + 1 ])
split = next (( c for c , v in cnt . items () if v < k ), '' )
if not split :
return r - l + 1
i = l
ans = 0
while i <= r :
while i <= r and s [ i ] == split :
i += 1
if i >= r :
break
j = i
while j <= r and s [ j ] != split :
j += 1
t = dfs ( i , j - 1 )
ans = max ( ans , t )
i = j
return ans
return dfs ( 0 , len ( s ) - 1 )
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45 class Solution {
private String s ;
private int k ;
public int longestSubstring ( String s , int k ) {
this . s = s ;
this . k = k ;
return dfs ( 0 , s . length () - 1 );
}
private int dfs ( int l , int r ) {
int [] cnt = new int [ 26 ] ;
for ( int i = l ; i <= r ; ++ i ) {
++ cnt [ s . charAt ( i ) - 'a' ] ;
}
char split = 0 ;
for ( int i = 0 ; i < 26 ; ++ i ) {
if ( cnt [ i ] > 0 && cnt [ i ] < k ) {
split = ( char ) ( i + 'a' );
break ;
}
}
if ( split == 0 ) {
return r - l + 1 ;
}
int i = l ;
int ans = 0 ;
while ( i <= r ) {
while ( i <= r && s . charAt ( i ) == split ) {
++ i ;
}
if ( i > r ) {
break ;
}
int j = i ;
while ( j <= r && s . charAt ( j ) != split ) {
++ j ;
}
int t = dfs ( i , j - 1 );
ans = Math . max ( ans , t );
i = j ;
}
return ans ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40 class Solution {
public :
int longestSubstring ( string s , int k ) {
function < int ( int , int ) > dfs = [ & ]( int l , int r ) -> int {
int cnt [ 26 ] = { 0 };
for ( int i = l ; i <= r ; ++ i ) {
cnt [ s [ i ] - 'a' ] ++ ;
}
char split = 0 ;
for ( int i = 0 ; i < 26 ; ++ i ) {
if ( cnt [ i ] > 0 && cnt [ i ] < k ) {
split = 'a' + i ;
break ;
}
}
if ( split == 0 ) {
return r - l + 1 ;
}
int i = l ;
int ans = 0 ;
while ( i <= r ) {
while ( i <= r && s [ i ] == split ) {
++ i ;
}
if ( i >= r ) {
break ;
}
int j = i ;
while ( j <= r && s [ j ] != split ) {
++ j ;
}
int t = dfs ( i , j - 1 );
ans = max ( ans , t );
i = j ;
}
return ans ;
};
return dfs ( 0 , s . size () - 1 );
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38 func longestSubstring ( s string , k int ) int {
var dfs func ( l , r int ) int
dfs = func ( l , r int ) int {
cnt := [ 26 ] int {}
for i := l ; i <= r ; i ++ {
cnt [ s [ i ] - 'a' ] ++
}
var split byte
for i , v := range cnt {
if v > 0 && v < k {
split = byte ( i + 'a' )
break
}
}
if split == 0 {
return r - l + 1
}
i := l
ans := 0
for i <= r {
for i <= r && s [ i ] == split {
i ++
}
if i > r {
break
}
j := i
for j <= r && s [ j ] != split {
j ++
}
t := dfs ( i , j - 1 )
ans = max ( ans , t )
i = j
}
return ans
}
return dfs ( 0 , len ( s ) - 1 )
}
GitHub