Formatted question description: https://leetcode.ca/all/1898.html

1898. Maximum Number of Removable Characters

Level

Medium

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, “abcacb” becomes “accb”.

“ab” is a subsequence of “accb”.

If we remove the characters at indices 3, 1, and 0, “abcacb” 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, “abcbddddd” becomes “abcddddd”.

“abcd” is a subsequence of “abcddddd”.

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 <= 10^5
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.

Solution

Use binary search. Initially, low = 0 and high = removable.length. Each time, let mid be the mean of low and high and check whether p is still a subsequence of s after removing mid characters from s according to removable. The maximum possible k can be found in this way.

class Solution {
    public int maximumRemovals(String s, String p, int[] removable) {
        int low = 0, high = removable.length;
        while (low < high) {
            int mid = (high - low + 1) / 2 + low;
            if (isPossible(s, p, removable, mid))
                low = mid;
            else
                high = mid - 1;
        }
        return low;
    }

    public boolean isPossible(String s, String p, int[] removable, int k) {
        int[] removes = new int[k];
        for (int i = 0; i < k; i++)
            removes[i] = removable[i];
        Arrays.sort(removes);
        StringBuffer sb = new StringBuffer(s);
        for (int i = k - 1; i >= 0; i--)
            sb.deleteCharAt(removes[i]);
        return isSubsequence(p, sb.toString());
    }

    public boolean isSubsequence(String s, String t) {
        if (s.length() == 0)
            return true;
        if (s.length() > t.length())
            return false;
        int sLength = s.length(), tLength = t.length();
        int sIndex = 0, tIndex = 0;
        while (sIndex < sLength && tIndex < tLength) {
            char sChar = s.charAt(sIndex), tChar = t.charAt(tIndex);
            if (sChar == tChar)
                sIndex++;
            tIndex++;
        }
        return sIndex == sLength;
    }
}

############

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;
    }
}

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

############

# 1898. Maximum Number of Removable Characters
# https://leetcode.com/problems/maximum-number-of-removable-characters/

class Solution:
    def maximumRemovals(self, s: str, p: str, removable: List[int]) -> int:
        n = len(s)
        pn = len(p)
        rn = len(removable)
        
        def good(x):
            x = rn - x
            sset = set(removable[:x])
            j = 0
            
            for i, x in enumerate(s):
                if x == p[j] and i not in sset:
                    j += 1
                
                if j == pn: return True
            
            return False
            
        left, right = 0, rn
        while left < right:
            mid = (left + right) // 2

            if good(mid):
                right = mid
            else:
                left = mid + 1

        return rn - left
        
                

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;
    }
};

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
}

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;
}

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
    }
}

1898 - Maximum Number of Removable Characters

1898. Maximum Number of Removable Characters

Level

Description

Solution

All Problems

All Solutions

Welcome to Subscribe On Youtube

1898. Maximum Number of Removable Characters

Level

Description

Solution

All Problems

All Solutions