Hash Table
String
Description
Given a string s
, return the length of the longest substring between two equal characters, excluding the two characters. If there is no such substring return -1
.
A substring is a contiguous sequence of characters within a string.
Example 1:
Input: s = "aa"
Output: 0
Explanation: The optimal substring here is an empty substring between the two 'a's.
Example 2:
Input: s = "abca"
Output: 2
Explanation: The optimal substring here is "bc".
Example 3:
Input: s = "cbzxy"
Output: -1
Explanation: There are no characters that appear twice in s.
Constraints:
1 <= s.length <= 300
s
contains only lowercase English letters.
Solutions
Solution 1
Python3 Java C++ Go TypeScript Rust C
class Solution :
def maxLengthBetweenEqualCharacters ( self , s : str ) -> int :
d = {}
ans = - 1
for i , c in enumerate ( s ):
if c in d :
ans = max ( ans , i - d [ c ] - 1 )
else :
d [ c ] = i
return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 class Solution {
public int maxLengthBetweenEqualCharacters ( String s ) {
int [] d = new int [ 26 ] ;
Arrays . fill ( d , - 1 );
int ans = - 1 ;
for ( int i = 0 ; i < s . length (); ++ i ) {
int j = s . charAt ( i ) - 'a' ;
if ( d [ j ] == - 1 ) {
d [ j ] = i ;
} else {
ans = Math . max ( ans , i - d [ j ] - 1 );
}
}
return ans ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 class Solution {
public :
int maxLengthBetweenEqualCharacters ( string s ) {
vector < int > d ( 26 , -1 );
int ans = -1 ;
for ( int i = 0 ; i < s . size (); ++ i ) {
int j = s [ i ] - 'a' ;
if ( d [ j ] == -1 ) {
d [ j ] = i ;
} else {
ans = max ( ans , i - d [ j ] - 1 );
}
}
return ans ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 func maxLengthBetweenEqualCharacters ( s string ) int {
d := make ([] int , 26 )
for i := range d {
d [ i ] = - 1
}
ans := - 1
for i , c := range s {
c -= 'a'
if d [ c ] == - 1 {
d [ c ] = i
} else {
ans = max ( ans , i - d [ c ] - 1 )
}
}
return ans
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14 function maxLengthBetweenEqualCharacters ( s : string ) : number {
const n = s . length ;
const pos = new Array ( 26 ). fill ( - 1 );
let res = - 1 ;
for ( let i = 0 ; i < n ; i ++ ) {
const j = s [ i ]. charCodeAt ( 0 ) - 'a' . charCodeAt ( 0 );
if ( pos [ j ] === - 1 ) {
pos [ j ] = i ;
} else {
res = Math . max ( res , i - pos [ j ] - 1 );
}
}
return res ;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 impl Solution {
pub fn max_length_between_equal_characters ( s : String ) -> i32 {
let s = s . as_bytes ();
let n = s . len ();
let mut pos = [ - 1 ; 26 ];
let mut res = - 1 ;
for i in 0 .. n {
let j = ( s [ i ] - b'a' ) as usize ;
let i = i as i32 ;
if pos [ j ] == - 1 {
pos [ j ] = i ;
} else {
res = res . max ( i - pos [ j ] - 1 );
}
}
res
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 #define max(a, b) (((a) > (b)) ? (a) : (b))
int maxLengthBetweenEqualCharacters ( char * s ) {
int pos [ 26 ];
memset ( pos , -1 , sizeof ( pos ));
int n = strlen ( s );
int res = -1 ;
for ( int i = 0 ; i < n ; i ++ ) {
char c = s [ i ];
int j = c - 'a' ;
if ( pos [ j ] == -1 ) {
pos [ j ] = i ;
} else {
res = max ( res , i - pos [ j ] - 1 );
}
}
return res ;
}