Introduction

In this blog post, we will explore how to solve the LeetCode problem "1898" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

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 <= 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.

Explanation

Here's a breakdown of the solution:

• Binary Search: We'll use binary search to find the maximum k. The search space is the range of possible k values (0 to removable.length).
• Subsequence Check: For each k value, we'll simulate removing the first k characters from s as indicated by removable. Then, we will check if p is still a subsequence of the modified s.

• Update Search Range: If p is a subsequence, it means k is a valid answer, and we can try a larger k. Otherwise, we must reduce the search range to try smaller values of k.

• Runtime & Storage Complexity: The runtime complexity is O(log(n) * (m + s)), where n is removable.length, m is p.length, and s is s.length. The storage complexity is O(s) because we create a copy of the string s in the isSubsequenceAfterRemoval helper function.

Code

    def maximumRemovals(s: str, p: str, removable: list[int]) -> int:
    """
    Finds the maximum k such that p is a subsequence of s after removing the first k characters from s.
    """

    def isSubsequenceAfterRemoval(k: int) -> bool:
        """
        Checks if p is a subsequence of s after removing the first k indices in removable.
        """
        removed_indices = set(removable[:k])
        modified_s = ""
        for i in range(len(s)):
            if i not in removed_indices:
                modified_s += s[i]

        p_ptr = 0
        s_ptr = 0
        while p_ptr < len(p) and s_ptr < len(modified_s):
            if p[p_ptr] == modified_s[s_ptr]:
                p_ptr += 1
            s_ptr += 1

        return p_ptr == len(p)

    left = 0
    right = len(removable)
    ans = 0

    while left <= right:
        mid = (left + right) // 2
        if isSubsequenceAfterRemoval(mid):
            ans = mid
            left = mid + 1
        else:
            right = mid - 1

    return ans