Hash Table
String
Counting
Hash Function
Rolling Hash
Description
Given a digit string s
, return the number of unique substrings of s
where every digit appears the same number of times.
Example 1:
Input: s = "1212"
Output: 5
Explanation: The substrings that meet the requirements are "1", "2", "12", "21", "1212".
Note that although the substring "12" appears twice, it is only counted once.
Example 2:
Input: s = "12321"
Output: 9
Explanation: The substrings that meet the requirements are "1", "2", "3", "12", "23", "32", "21", "123", "321".
Constraints:
1 <= s.length <= 1000
s
consists of digits.
Solutions
Solution 1
Python3 Java Go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 class Solution :
def equalDigitFrequency ( self , s : str ) -> int :
def check ( i , j ):
v = set ()
for k in range ( 10 ):
cnt = presum [ j + 1 ][ k ] - presum [ i ][ k ]
if cnt > 0 :
v . add ( cnt )
if len ( v ) > 1 :
return False
return True
n = len ( s )
presum = [[ 0 ] * 10 for _ in range ( n + 1 )]
for i , c in enumerate ( s ):
presum [ i + 1 ][ int ( c )] += 1
for j in range ( 10 ):
presum [ i + 1 ][ j ] += presum [ i ][ j ]
vis = set ( s [ i : j + 1 ] for i in range ( n ) for j in range ( i , n ) if check ( i , j ))
return len ( vis )
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 class Solution {
public int equalDigitFrequency ( String s ) {
int n = s . length ();
int [][] presum = new int [ n + 1 ][ 10 ] ;
for ( int i = 0 ; i < n ; ++ i ) {
++ presum [ i + 1 ][ s . charAt ( i ) - '0' ] ;
for ( int j = 0 ; j < 10 ; ++ j ) {
presum [ i + 1 ][ j ] += presum [ i ][ j ] ;
}
}
Set < String > vis = new HashSet <> ();
for ( int i = 0 ; i < n ; ++ i ) {
for ( int j = i ; j < n ; ++ j ) {
if ( check ( i , j , presum )) {
vis . add ( s . substring ( i , j + 1 ));
}
}
}
return vis . size ();
}
private boolean check ( int i , int j , int [][] presum ) {
Set < Integer > v = new HashSet <> ();
for ( int k = 0 ; k < 10 ; ++ k ) {
int cnt = presum [ j + 1 ][ k ] - presum [ i ][ k ] ;
if ( cnt > 0 ) {
v . add ( cnt );
}
if ( v . size () > 1 ) {
return false ;
}
}
return true ;
}
}
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 func equalDigitFrequency ( s string ) int {
n := len ( s )
presum := make ([][] int , n + 1 )
for i := range presum {
presum [ i ] = make ([] int , 10 )
}
for i , c := range s {
presum [ i + 1 ][ c - '0' ] ++
for j := 0 ; j < 10 ; j ++ {
presum [ i + 1 ][ j ] += presum [ i ][ j ]
}
}
check := func ( i , j int ) bool {
v := make ( map [ int ] bool )
for k := 0 ; k < 10 ; k ++ {
cnt := presum [ j + 1 ][ k ] - presum [ i ][ k ]
if cnt > 0 {
v [ cnt ] = true
}
if len ( v ) > 1 {
return false
}
}
return true
}
vis := make ( map [ string ] bool )
for i := 0 ; i < n ; i ++ {
for j := i ; j < n ; j ++ {
if check ( i , j ) {
vis [ s [ i : j + 1 ]] = true
}
}
}
return len ( vis )
}
GitHub