Watch 10 video solutions for Subsequence With the Minimum Score, a hard level problem involving Two Pointers, String, Binary Search. This walkthrough by Aryan Mittal has 2,690 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given two strings s and t.
You are allowed to remove any number of characters from the string t.
The score of the string is 0 if no characters are removed from the string t, otherwise:
left be the minimum index among all removed characters.right be the maximum index among all removed characters.Then the score of the string is right - left + 1.
Return the minimum possible score to make t a subsequence of s.
A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e., "ace" is a subsequence of "abcde" while "aec" is not).
Example 1:
Input: s = "abacaba", t = "bzaa" Output: 1 Explanation: 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 Explanation: 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 <= 105s and t consist of only lowercase English letters.Problem Overview: You are given two strings s and t. The goal is to remove a contiguous substring from t so that the remaining characters form a subsequence of s. The score equals the length of the removed substring, and you want the minimum possible score.
Approach 1: Dynamic Programming (O(n * m) time, O(n * m) space)
A straightforward way to reason about the problem is through subsequence matching similar to the Longest Common Subsequence idea. Use a dp[i][j] state to represent whether the first i characters of s can match the first j characters of t. From this information you can determine which prefixes of t are valid subsequences and then check suffixes that can still match later in s. By combining valid prefix and suffix matches, you compute the smallest middle segment that must be removed. This approach clearly models the subsequence constraint but requires O(n * m) transitions and memory, which becomes expensive when both strings are large.
This method is useful for understanding the structure of the problem: subsequences are formed by advancing pointers without reordering characters. Once that idea is clear, the problem can be optimized significantly.
Approach 2: Two-Pointer Method with Prefix/Suffix Matching (O(n + m) time, O(m) space)
The optimal solution relies on greedy subsequence matching using two pointers. First scan s from left to right and record the earliest index where each prefix of t can be matched. Store these indices in an array left[i]. Then scan from right to left to compute right[i], the latest index in s where the suffix starting at t[i] can still match.
Once prefix and suffix matches are known, you can remove a middle substring from t. The prefix t[0..i] must match before some index in s, and the suffix t[j..] must match after that. Move two pointers across these arrays to maintain the valid ordering left[i] < right[j]. The removal length becomes j - i - 1, and you minimize this value across all valid pairs.
This scan works because subsequence positions in s are monotonic. Each pointer only moves forward once, giving linear complexity. The approach combines ideas from string processing and occasionally a binary search variant that checks feasible deletion lengths.
Recommended for interviews: The two-pointer prefix/suffix strategy is the expected solution. It runs in O(n + m) time and demonstrates strong understanding of subsequence matching and pointer techniques. Mentioning the dynamic programming interpretation first shows conceptual clarity, but implementing the linear scan proves you can optimize string problems effectively under interview constraints.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming | O(n * m) | O(n * m) | Useful for understanding subsequence relationships or when constraints are small |
| Two-Pointer Prefix/Suffix Matching | O(n + m) | O(m) | Best practical solution for large strings and typical interview settings |
| Binary Search + Subsequence Check | O((n + m) log m) | O(m) | Alternative when reasoning about the minimum removable length as a monotonic search space |