Maximum Number of Removable Characters

Maximum Number of Removable Characters

What is this problem about?

The Maximum Number of Removable Characters coding problem gives you two strings, s and p, and an array of removable indices. You need to find the maximum number of characters you can remove from s (using the indices from removable) such that p remains a subsequence of the modified s.

Why is this asked in interviews?

Alphonso, Snowflake, Amazon, and Moveworks use this problem to test a candidate's proficiency with binary search on the answer, combined with a check function that involves two pointers. It's a classic pattern where the feasibility of an "answer" (number of removals) is monotonic, enabling a binary search optimization.

Algorithmic pattern used

Binary Search on the Answer + Two Pointers Check: The problem asks for the maximum number of removable characters. This value has a monotonic property: if we can remove k characters and p is still a subsequence, then we can certainly remove any k' < k characters and p will still be a subsequence. This monotonic property allows us to binary search for the maximum k.

The binary search will be performed on the range [0, len(removable)]. For a given mid value (representing mid characters removed):

1. check(mid) function:

   • Create a boolean array removed_flags of size len(s), initialized to false.
   • Mark removed_flags[removable[i]] = true for i from 0 to mid-1. (These are the first mid characters to be removed from s).
   • Use two pointers, ptr_s for s and ptr_p for p.
   • Iterate ptr_s through s. If s[ptr_s] is not marked as removed_flags[ptr_s] and s[ptr_s] == p[ptr_p], then increment ptr_p.
   • If ptr_p reaches len(p), it means p is a subsequence. Return true.
   • If ptr_s reaches len(s) but ptr_p has not reached len(p), return false.

2. Binary Search Logic:

   • low = 0, high = len(removable), ans = 0.
   • While low <= high:
     • mid = low + (high - low) // 2.
     • If check(mid) is true: it means mid characters can be removed. Try to remove more: ans = mid, low = mid + 1.
     • If check(mid) is false: mid characters cannot be removed. Try removing fewer: high = mid - 1.
   • Return ans.

Time Complexity: O(len(removable) * (len(s) + len(p))). The log(len(removable)) factor comes from binary search, and len(s) + len(p) from the two-pointer check. Note: len(removable) for creating removed_flags is the dominant factor in check unless len(s) is much larger.

Example explanation

s = "abcacb", p = "ab", removable = [3, 1, 0]. len(removable) = 3. Binary search [0, 3].

low = 0, high = 3, ans = 0.

1. mid = 1: removable_indices = {3}. s after removing s[3]: "ab_acb" -> "abacb". Is "ab" a subsequence of "abacb"? Yes. ans = 1, low = 2.

2. mid = 2: removable_indices = {3, 1}. s after removing s[3], s[1]: "a_a_cb" -> "aacb". Is "ab" a subsequence of "aacb"? ptr_s at 'a' (idx 0, not removed), ptr_p at 'a' (idx 0). Match. ptr_p++. ptr_s at 'a' (idx 2, not removed), ptr_p at 'b' (idx 1). No match. ptr_s at 'c' (idx 4, not removed), ptr_p at 'b' (idx 1). No match. ptr_s at 'b' (idx 5, not removed), ptr_p at 'b' (idx 1). Match. ptr_p++. ptr_p is 2, which is len(p). Yes. ans = 2, low = 3.

3. mid = 3: removable_indices = {3, 1, 0}. s after removing s[3], s[1], s[0]: "__a_cb" -> "acb". Is "ab" a subsequence of "acb"? ptr_s at 'a' (idx 2, not removed), ptr_p at 'a' (idx 0). Match. ptr_p++. ptr_s at 'c' (idx 4, not removed), ptr_p at 'b' (idx 1). No match. ptr_s at 'b' (idx 5, not removed), ptr_p at 'b' (idx 1). Match. ptr_p++. ptr_p is 2, which is len(p). Yes. ans = 3, low = 4.

Loop terminates (low=4, high=3). ans = 3.

Common mistakes candidates make

• Flawed check function: The core of binary search on answer problems. Ensure the check function correctly determines feasibility for the given mid value. This includes accurately handling character removals and subsequence checks.
• Incorrect binary search range or update logic: low = mid + 1 and high = mid - 1 are crucial for converging.
• Time complexity of check: The check function itself must be efficient (e.g., O(len(s) + len(p))).

Interview preparation tip

For the Array Two Pointers Binary Search String interview pattern, problems often reduce to a check function with two pointers or similar linear scans, wrapped in a binary search. Practice recognizing monotonic properties and designing efficient check functions.