Array
Two Pointers
String
Binary Search
Description
You are given two strings s
and p
where p
is a subsequence of s
. You are also given a distinct 0-indexed integer array removable
containing a subset of indices of s
(s
is also 0-indexed ).
You want to choose an integer k
(0 <= k <= removable.length
) such that, after removing k
characters from s
using the first k
indices in removable
, p
is still a subsequence of s
. More formally, you will mark the character at s[removable[i]]
for each 0 <= i < k
, then remove all marked characters and check if p
is still a subsequence.
Return the maximum k
you can choose such that p
is still a subsequence of s
after the removals .
A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.
Example 1:
Input: s = "abcacb", p = "ab", removable = [3,1,0]
Output: 2
Explanation : After removing the characters at indices 3 and 1, "ab ca cb" becomes "accb".
"ab" is a subsequence of "a ccb ".
If we remove the characters at indices 3, 1, and 0, "ab ca cb" becomes "ccb", and "ab" is no longer a subsequence.
Hence, the maximum k is 2.
Example 2:
Input: s = "abcbddddd", p = "abcd", removable = [3,2,1,4,5,6]
Output: 1
Explanation : After removing the character at index 3, "abcb ddddd" becomes "abcddddd".
"abcd" is a subsequence of "abcd dddd".
Example 3:
Input: s = "abcab", p = "abc", removable = [0,1,2,3,4]
Output: 0
Explanation : If you remove the first index in the array removable, "abc" is no longer a subsequence.
Constraints:
1 <= p.length <= s.length <= 105
0 <= removable.length < s.length
0 <= removable[i] < s.length
p
is a subsequence of s
.
s
and p
both consist of lowercase English letters.
The elements in removable
are distinct .
Solutions
Solution 1
Python3 Java C++ Go TypeScript Rust JavaScript Kotlin
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 class Solution :
def maximumRemovals ( self , s : str , p : str , removable : List [ int ]) -> int :
def check ( k ):
i = j = 0
ids = set ( removable [: k ])
while i < m and j < n :
if i not in ids and s [ i ] == p [ j ]:
j += 1
i += 1
return j == n
m , n = len ( s ), len ( p )
left , right = 0 , len ( removable )
while left < right :
mid = ( left + right + 1 ) >> 1
if check ( mid ):
left = mid
else :
right = mid - 1
return left
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 class Solution {
public int maximumRemovals ( String s , String p , int [] removable ) {
int left = 0 , right = removable . length ;
while ( left < right ) {
int mid = ( left + right + 1 ) >> 1 ;
if ( check ( s , p , removable , mid )) {
left = mid ;
} else {
right = mid - 1 ;
}
}
return left ;
}
private boolean check ( String s , String p , int [] removable , int mid ) {
int m = s . length (), n = p . length (), i = 0 , j = 0 ;
Set < Integer > ids = new HashSet <> ();
for ( int k = 0 ; k < mid ; ++ k ) {
ids . add ( removable [ k ] );
}
while ( i < m && j < n ) {
if ( ! ids . contains ( i ) && s . charAt ( i ) == p . charAt ( j )) {
++ j ;
}
++ i ;
}
return j == n ;
}
}
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 class Solution {
public :
int maximumRemovals ( string s , string p , vector < int >& removable ) {
int left = 0 , right = removable . size ();
while ( left < right ) {
int mid = left + right + 1 >> 1 ;
if ( check ( s , p , removable , mid )) {
left = mid ;
} else {
right = mid - 1 ;
}
}
return left ;
}
bool check ( string s , string p , vector < int >& removable , int mid ) {
int m = s . size (), n = p . size (), i = 0 , j = 0 ;
unordered_set < int > ids ;
for ( int k = 0 ; k < mid ; ++ k ) {
ids . insert ( removable [ k ]);
}
while ( i < m && j < n ) {
if ( ids . count ( i ) == 0 && s [ i ] == p [ j ]) {
++ j ;
}
++ i ;
}
return j == n ;
}
};
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 func maximumRemovals ( s string , p string , removable [] int ) int {
check := func ( k int ) bool {
ids := make ( map [ int ] bool )
for _ , r := range removable [: k ] {
ids [ r ] = true
}
var i , j int
for i < len ( s ) && j < len ( p ) {
if ! ids [ i ] && s [ i ] == p [ j ] {
j ++
}
i ++
}
return j == len ( p )
}
left , right := 0 , len ( removable )
for left < right {
mid := ( left + right + 1 ) >> 1
if check ( mid ) {
left = mid
} else {
right = mid - 1
}
}
return left
}
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 function maximumRemovals ( s : string , p : string , removable : number []) : number {
let left = 0 ,
right = removable . length ;
while ( left < right ) {
let mid = ( left + right + 1 ) >> 1 ;
if ( isSub ( s , p , new Set ( removable . slice ( 0 , mid )))) {
left = mid ;
} else {
right = mid - 1 ;
}
}
return left ;
}
function isSub ( str : string , sub : string , idxes : Set < number > ) : boolean {
let m = str . length ,
n = sub . length ;
let i = 0 ,
j = 0 ;
while ( i < m && j < n ) {
if ( ! idxes . has ( i ) && str . charAt ( i ) == sub . charAt ( j )) {
++ j ;
}
++ i ;
}
return j == n ;
}
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 use std :: collections :: HashSet ;
impl Solution {
pub fn maximum_removals ( s : String , p : String , removable : Vec < i32 > ) -> i32 {
let m = s . len ();
let n = p . len ();
let s = s . as_bytes ();
let p = p . as_bytes ();
let check = | k | {
let mut i = 0 ;
let mut j = 0 ;
let ids : HashSet < i32 > = removable [ .. k ]. iter (). cloned (). collect ();
while i < m && j < n {
if ! ids . contains ( & ( i as i32 )) && s [ i ] == p [ j ] {
j += 1 ;
}
i += 1 ;
}
j == n
};
let mut left = 0 ;
let mut right = removable . len ();
while left + 1 < right {
let mid = left + ( right - left ) / 2 ;
if check ( mid ) {
left = mid ;
} else {
right = mid ;
}
}
if check ( right ) {
return right as i32 ;
}
left as i32
}
}
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 /**
* @param {string} s
* @param {string} p
* @param {number[]} removable
* @return {number}
*/
function maximumRemovals ( s , p , removable ) {
const str_len = s . length ;
const sub_len = p . length ;
/**
* @param {number} k
* @return {boolean}
*/
function isSub ( k ) {
const removed = new Set ( removable . slice ( 0 , k ));
let sub_i = 0 ;
for ( let str_i = 0 ; str_i < str_len ; ++ str_i ) {
if ( s . charAt ( str_i ) === p . charAt ( sub_i ) && ! removed . has ( str_i )) {
++ sub_i ;
if ( sub_i >= sub_len ) {
break ;
}
}
}
return sub_i === sub_len ;
}
let left = 0 ;
let right = removable . length ;
while ( left < right ) {
const middle = ( left + right ) >> 1 ;
if ( isSub ( middle + 1 )) {
left = middle + 1 ;
} else {
right = middle ;
}
}
return left ;
}
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 {
fun maximumRemovals ( s : String , p : String , removable : IntArray ): Int {
val strLen = s . length
val subLen = p . length
fun isSub ( k : Int ): Boolean {
val removed = removable . sliceArray ( 0 .. < k ). toHashSet ()
var subIndex = 0
for ( strIndex in 0 .. < strLen ) {
if ( s [ strIndex ] == p [ subIndex ] && ! removed . contains ( strIndex )) {
++ subIndex
if ( subIndex >= subLen ) {
break
}
}
}
return subIndex == subLen
}
var left = 0
var right = removable . size
while ( left < right ) {
val middle = ( left + right ) / 2
if ( isSub ( middle + 1 )) {
left = middle + 1
} else {
right = middle
}
}
return left
}
}