Problem

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.

Subarrays vs Subsequences vs Subsets Definition

Examples

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.

Solution

Method 1 - Brute Force

We can use Is Subsequence Problem to check if 2 strings are subsequence in O(n) time. We will do it till we have k chars removed. So, time complexity will be O(k*n). This solution may result in TLE.

Method 2- Binary Search

Why do I use binary search? It helps me determine the maximum number of elements that can be removed while ensuring p remains a subsequence of s. The removable array is cumulative, meaning we sequentially remove characters at the given indices, for example, starting from index 3, then 2, and finally 1. This approach effectively reduces to a linear search if not optimized properly. Hence, binary search is utilized for efficiency.

  • The left boundary represents the lower limit (initially 0), and the right boundary represents the upper limit (the length of the removable array).
  • In each iteration, I calculate the middle point (representing an attempt to remove that many characters from the string).
  • I use a character array and mark removed characters with a special symbol (like /) to indicate deletion without actually modifying the string.
  • This approach is faster and more convenient compared to directly removing characters from the string, which has high time complexity due to string concatenation operations.

IsSubsequence method

The isSubsequence method operates similarly to the Is Subsequence Problem with some modifications:

  • I use two pointers: one to traverse the character array and another to track the current character in p.
  • If the current character in the array hasn’t been ‘removed’ (denoted by the / symbol) and it matches the corresponding character in p, I increment both pointers.
  • If the characters don’t match or the current character is ‘removed’, I only increment the pointer for the character array.

Code

Java
class Solution {
	public int maximumRemovals(String s, String p, int[] removable) {
		char[] letters = s.toCharArray();
		int l = 0, r = removable.length;
		while (l<= r) {
			//'mid' represents how many letters I remove this round.
			int mid = (l + r) / 2;
			//'Remove' those letters! 
			for (int i = 0; i<mid; i++) {
				letters[removable[i]] = '/';
			}
	
			//I perform a simple check to see if p is still a subsequence of it. If it is, change the lower boundary.
			if (isSubsequence(p, letters)) {
				l = mid + 1;
			}
	
			//Otherwise, I replace back all the letters that I had removed.
			//Then, I change the upper boundary.
			else {
				for (int i = 0; i<mid; i++) {
					letters[removable[i]] = s.charAt(removable[i]);
				}
				r = mid - 1;
			}
		}
		return r;
	}
	// is p subsequence of letters
	public boolean isSubsequence(String p, char[] letters) {
		int i = 0, j = 0;
		while (i < letters.length && j < p.length()) {
			char curr = letters[i], curr2 = p.charAt(j);
			if (curr != '/' && curr == curr2) j++;
			i++;
		}
		
		if (j == p.length()) return true;
		return false;
	}
}
Python
class Solution:
    def maximumRemovals(self, s: str, p: str, removable: List[int]) -> int:
        letters = list(s)
        l = 0
        r = len(removable)
        
        while l <= r:
            # 'mid' represents how many letters we remove this round.
            mid = (l + r) // 2
            
            # 'Remove' those letters!
            for i in range(mid):
                letters[removable[i]] = '/'
            
            # Perform a check to see if p is still a subsequence.
            if self.is_subsequence(p, letters):
                l = mid + 1
            else:
                # Otherwise, revert changes.
                for i in range(mid):
                    letters[removable[i]] = s[removable[i]]
                r = mid - 1
        
        return r

    def is_subsequence(self, p: str, letters: List[str]) -> bool:
        i = 0
        j = 0
        
        while i < len(letters) and j < len(p):
            if letters[i] != '/' and letters[i] == p[j]:
                j += 1
            i += 1
        
        return j == len(p)

Complexity

  • ⏰ Time complexity: O(m * log n), where m is the length of the string s, and n is the length of the removable array. The log factor comes from the binary search and m from the subsequence check.
  • 🧺 Space complexity: O(n) for the set used to keep track of removed characters.