Hash Table
String
Sliding Window
Description
Given two strings s
and p
, return an array of all the start indices of p
's anagrams in s
. You may return the answer in any order .
Example 1:
Input: s = "cbaebabacd", p = "abc"
Output: [0,6]
Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".
Example 2:
Input: s = "abab", p = "ab"
Output: [0,1,2]
Explanation:
The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".
Constraints:
1 <= s.length, p.length <= 3 * 104
s
and p
consist of lowercase English letters.
Solutions
Solution 1
Python3 Java C++ Go TypeScript Rust C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14 class Solution :
def findAnagrams ( self , s : str , p : str ) -> List [ int ]:
m , n = len ( s ), len ( p )
ans = []
if m < n :
return ans
cnt1 = Counter ( p )
cnt2 = Counter ( s [: n - 1 ])
for i in range ( n - 1 , m ):
cnt2 [ s [ i ]] += 1
if cnt1 == cnt2 :
ans . append ( i - n + 1 )
cnt2 [ s [ i - n + 1 ]] -= 1
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 class Solution {
public List < Integer > findAnagrams ( String s , String p ) {
int m = s . length (), n = p . length ();
List < Integer > ans = new ArrayList <> ();
if ( m < n ) {
return ans ;
}
int [] cnt1 = new int [ 26 ] ;
for ( int i = 0 ; i < n ; ++ i ) {
++ cnt1 [ p . charAt ( i ) - 'a' ] ;
}
int [] cnt2 = new int [ 26 ] ;
for ( int i = 0 ; i < n - 1 ; ++ i ) {
++ cnt2 [ s . charAt ( i ) - 'a' ] ;
}
for ( int i = n - 1 ; i < m ; ++ i ) {
++ cnt2 [ s . charAt ( i ) - 'a' ] ;
if ( Arrays . equals ( cnt1 , cnt2 )) {
ans . add ( i - n + 1 );
}
-- cnt2 [ s . charAt ( i - n + 1 ) - 'a' ] ;
}
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 class Solution {
public :
vector < int > findAnagrams ( string s , string p ) {
int m = s . size (), n = p . size ();
vector < int > ans ;
if ( m < n ) {
return ans ;
}
vector < int > cnt1 ( 26 );
for ( char & c : p ) {
++ cnt1 [ c - 'a' ];
}
vector < int > cnt2 ( 26 );
for ( int i = 0 ; i < n - 1 ; ++ i ) {
++ cnt2 [ s [ i ] - 'a' ];
}
for ( int i = n - 1 ; i < m ; ++ i ) {
++ cnt2 [ s [ i ] - 'a' ];
if ( cnt1 == cnt2 ) {
ans . push_back ( i - n + 1 );
}
-- cnt2 [ s [ i - n + 1 ] - 'a' ];
}
return ans ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 func findAnagrams ( s string , p string ) ( ans [] int ) {
m , n := len ( s ), len ( p )
if m < n {
return
}
cnt1 := [ 26 ] int {}
cnt2 := [ 26 ] int {}
for _ , c := range p {
cnt1 [ c - 'a' ] ++
}
for _ , c := range s [: n - 1 ] {
cnt2 [ c - 'a' ] ++
}
for i := n - 1 ; i < m ; i ++ {
cnt2 [ s [ i ] - 'a' ] ++
if cnt1 == cnt2 {
ans = append ( ans , i - n + 1 )
}
cnt2 [ s [ i - n + 1 ] - 'a' ] --
}
return
}
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 function findAnagrams ( s : string , p : string ) : number [] {
const m = s . length ;
const n = p . length ;
const ans : number [] = [];
if ( m < n ) {
return ans ;
}
const cnt1 : number [] = new Array ( 26 ). fill ( 0 );
const cnt2 : number [] = new Array ( 26 ). fill ( 0 );
const idx = ( c : string ) => c . charCodeAt ( 0 ) - 'a' . charCodeAt ( 0 );
for ( const c of p ) {
++ cnt1 [ idx ( c )];
}
for ( const c of s . slice ( 0 , n - 1 )) {
++ cnt2 [ idx ( c )];
}
for ( let i = n - 1 ; i < m ; ++ i ) {
++ cnt2 [ idx ( s [ i ])];
if ( cnt1 . toString () === cnt2 . toString ()) {
ans . push ( i - n + 1 );
}
-- cnt2 [ idx ( s [ i - n + 1 ])];
}
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 impl Solution {
pub fn find_anagrams ( s : String , p : String ) -> Vec < i32 > {
let ( s , p ) = ( s . as_bytes (), p . as_bytes ());
let ( m , n ) = ( s . len (), p . len ());
let mut ans = vec! [];
if m < n {
return ans ;
}
let mut cnt = [ 0 ; 26 ];
for i in 0 .. n {
cnt [( p [ i ] - b'a' ) as usize ] += 1 ;
cnt [( s [ i ] - b'a' ) as usize ] -= 1 ;
}
for i in n .. m {
if cnt . iter (). all ( |& v | v == 0 ) {
ans . push (( i - n ) as i32 );
}
cnt [( s [ i ] - b'a' ) as usize ] -= 1 ;
cnt [( s [ i - n ] - b'a' ) as usize ] += 1 ;
}
if cnt . iter (). all ( |& v | v == 0 ) {
ans . push (( m - n ) as i32 );
}
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 public class Solution {
public IList < int > FindAnagrams ( string s , string p ) {
int m = s . Length , n = p . Length ;
IList < int > ans = new List < int > ();
if ( m < n ) {
return ans ;
}
int [] cnt1 = new int [ 26 ];
int [] cnt2 = new int [ 26 ];
for ( int i = 0 ; i < n ; ++ i ) {
++ cnt1 [ p [ i ] - 'a' ];
}
for ( int i = 0 , j = 0 ; i < m ; ++ i ) {
int k = s [ i ] - 'a' ;
++ cnt2 [ k ];
while ( cnt2 [ k ] > cnt1 [ k ]) {
-- cnt2 [ s [ j ++ ] - 'a' ];
}
if ( i - j + 1 == n ) {
ans . Add ( j );
}
}
return ans ;
}
}
Solution 2
Python3 Java C++ Go TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 class Solution :
def findAnagrams ( self , s : str , p : str ) -> List [ int ]:
m , n = len ( s ), len ( p )
ans = []
if m < n :
return ans
cnt1 = Counter ( p )
cnt2 = Counter ()
j = 0
for i , c in enumerate ( s ):
cnt2 [ c ] += 1
while cnt2 [ c ] > cnt1 [ c ]:
cnt2 [ s [ j ]] -= 1
j += 1
if i - j + 1 == n :
ans . append ( 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 class Solution {
public List < Integer > findAnagrams ( String s , String p ) {
int m = s . length (), n = p . length ();
List < Integer > ans = new ArrayList <> ();
if ( m < n ) {
return ans ;
}
int [] cnt1 = new int [ 26 ] ;
for ( int i = 0 ; i < n ; ++ i ) {
++ cnt1 [ p . charAt ( i ) - 'a' ] ;
}
int [] cnt2 = new int [ 26 ] ;
for ( int i = 0 , j = 0 ; i < m ; ++ i ) {
int k = s . charAt ( i ) - 'a' ;
++ cnt2 [ k ] ;
while ( cnt2 [ k ] > cnt1 [ k ] ) {
-- cnt2 [ s . charAt ( j ++ ) - 'a' ] ;
}
if ( i - j + 1 == n ) {
ans . add ( 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 class Solution {
public :
vector < int > findAnagrams ( string s , string p ) {
int m = s . size (), n = p . size ();
vector < int > ans ;
if ( m < n ) {
return ans ;
}
vector < int > cnt1 ( 26 );
for ( char & c : p ) {
++ cnt1 [ c - 'a' ];
}
vector < int > cnt2 ( 26 );
for ( int i = 0 , j = 0 ; i < m ; ++ i ) {
int k = s [ i ] - 'a' ;
++ cnt2 [ k ];
while ( cnt2 [ k ] > cnt1 [ k ]) {
-- cnt2 [ s [ j ++ ] - 'a' ];
}
if ( i - j + 1 == n ) {
ans . push_back ( 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 func findAnagrams ( s string , p string ) ( ans [] int ) {
m , n := len ( s ), len ( p )
if m < n {
return
}
cnt1 := [ 26 ] int {}
cnt2 := [ 26 ] int {}
for _ , c := range p {
cnt1 [ c - 'a' ] ++
}
j := 0
for i , c := range s {
cnt2 [ c - 'a' ] ++
for cnt2 [ c - 'a' ] > cnt1 [ c - 'a' ] {
cnt2 [ s [ j ] - 'a' ] --
j ++
}
if i - j + 1 == n {
ans = append ( ans , j )
}
}
return
}
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 function findAnagrams ( s : string , p : string ) : number [] {
const m = s . length ;
const n = p . length ;
const ans : number [] = [];
if ( m < n ) {
return ans ;
}
const cnt1 : number [] = Array ( 26 ). fill ( 0 );
const cnt2 : number [] = Array ( 26 ). fill ( 0 );
const idx = ( c : string ) => c . charCodeAt ( 0 ) - 'a' . charCodeAt ( 0 );
for ( const c of p ) {
++ cnt1 [ idx ( c )];
}
for ( let i = 0 , j = 0 ; i < m ; ++ i ) {
const k = idx ( s [ i ]);
++ cnt2 [ k ];
while ( cnt2 [ k ] > cnt1 [ k ]) {
-- cnt2 [ idx ( s [ j ++ ])];
}
if ( i - j + 1 === n ) {
ans . push ( j );
}
}
return ans ;
}