#2565

Hard

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Subsequence With the Minimum Score

Find the minimum score of a string by removing characters from t while maintaining subsequence validity with s.

Problem Statement

Given two strings s and t, your task is to find the minimum score by removing any number of characters from t. If no characters are removed, the score is zero. Otherwise, the score is calculated as follows: subtract the number of removed characters and add one to account for any changes.

To solve this problem, we need to ensure that the remaining string t after removals still forms a subsequence of s. The challenge is determining how many characters to remove from t to minimize the score, using efficient methods like binary search and two pointers.

Examples

Example 1

Input: s = "abacaba", t = "bzaa"

Output: 1

In this example, we remove the character "z" at index 1 (0-indexed). The string t becomes "baa" which is a subsequence of the string "abacaba" and the score is 1 - 1 + 1 = 1. It can be proven that 1 is the minimum score that we can achieve.

Example 2

Input: s = "cde", t = "xyz"

Output: 3

In this example, we remove characters "x", "y" and "z" at indices 0, 1, and 2 (0-indexed). The string t becomes "" which is a subsequence of the string "cde" and the score is 2 - 0 + 1 = 3. It can be proven that 3 is the minimum score that we can achieve.

Constraints

1 <= s.length, t.length <= 105
s and t consist of only lowercase English letters.

Solution Approach

Binary Search on Answer Space

The key to this problem is binary search, where we explore the possible number of characters to remove from t. This allows us to find the minimum score by narrowing down the valid answer space efficiently.

Two Pointers to Maintain Subsequence Validity

Using two pointers (i and j), we simulate the removal of characters from t and check if the resulting string is a subsequence of s. Adjust the pointers as necessary to verify valid subsequences and minimize the score.

Minimizing Removals and Maximizing Validity

The goal is to balance the number of removals with subsequence validity. We remove characters from t until we achieve the smallest possible score, ensuring the resulting t is still a subsequence of s.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time and space complexities depend on the specific implementation of binary search and two-pointer techniques. In the best case, the approach achieves an optimal O(log(n) * m) complexity, where n is the length of string s and m is the length of string t.

What Interviewers Usually Probe

Candidate's understanding of binary search over valid answer space.
Ability to implement and use two-pointer techniques to validate subsequences.
Proficiency in balancing efficiency with correctness when solving string manipulation problems.

Common Pitfalls or Variants

Common pitfalls

Over-complicating the subsequence check, resulting in inefficient solutions.
Misusing binary search bounds, leading to incorrect results.
Failing to correctly update pointers during the subsequence validation.

Follow-up variants

Consider variations where certain characters are already removed from t.
What if both strings are sorted, and additional optimizations can be applied?
Explore cases where the subsequence check isn't strictly left-to-right.

FAQ

What is the primary pattern used in the Subsequence With the Minimum Score problem?

The primary pattern is binary search over the valid answer space, combined with two-pointer techniques for subsequence validation.

How does binary search help in this problem?

Binary search efficiently narrows down the valid number of characters to remove from t, minimizing the score while maintaining subsequence validity.

What is the time complexity of solving Subsequence With the Minimum Score?

The time complexity depends on the binary search and two-pointer approach, typically O(log(n) * m), where n is the length of s and m is the length of t.

Can the two-pointer technique fail in this problem?

Yes, if the pointers are not updated correctly or if they are used inefficiently, the solution can become suboptimal or incorrect.

How does GhostInterview assist with Subsequence With the Minimum Score?

GhostInterview helps by guiding you through binary search implementation, optimizing pointer adjustments, and avoiding common pitfalls during subsequence validation.

terminal

Solution

Solution 1: Prefix and Suffix Preprocessing + Binary Search

According to the problem, we know that the range of the index to delete characters is `[left, right]`. The optimal approach is to delete all characters within the range `[left, right]`. In other words, we need to delete a substring from string $t$, so that the remaining prefix of string $t$ can match the prefix of string $s$, and the remaining suffix of string $t$ can match the suffix of string $s$, and the prefix and suffix of string $s$ do not overlap. Note that the match here refers to subsequence matching.

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

class Solution:
    def minimumScore(self, s: str, t: str) -> int:
        def check(x):
            for k in range(n):
                i, j = k - 1, k + x
                l = f[i] if i >= 0 else -1
                r = g[j] if j < n else m + 1
                if l < r:
                    return True
            return False

        m, n = len(s), len(t)
        f = [inf] * n
        g = [-1] * n
        i, j = 0, 0
        while i < m and j < n:
            if s[i] == t[j]:
                f[j] = i
                j += 1
            i += 1
        i, j = m - 1, n - 1
        while i >= 0 and j >= 0:
            if s[i] == t[j]:
                g[j] = i
                j -= 1
            i -= 1

        return bisect_left(range(n + 1), True, key=check)

Continue Practicing

#3006 find beautiful indices in the given array i #3008 find beautiful indices in the given array ii #1898 maximum number of removable characters