Subsequence With the Minimum Score solution and explanation
9 more videos on this problem
Subsequence With the Minimum Score - Leetcode 2655 || Weekly Contest - 332Aryan Mittal · 24:18 · 2K views
2565. Subsequence With the Minimum Score | Weekly Contest 332 | LeetCode 2565Bro Coders · 21:04 · 1K views
Subsequence With the Minimum Score | Weekly Contest 332 | LeetcodecodingMohan · 28:26 · 1K views
2565. Subsequence With the Minimum Score | LeetCode HardDeep Tech · 14:51 · 989 views
Subsequence With the Minimum Score | O(n) | Leetcode 2565 | Weekly contest | DSA | Think then CodeThink then Code · 25:38 · 765 views
【每日一题】LeetCode 2565. Subsequence With the Minimum ScoreHuifeng Guan · 24:55 · 687 views
2565. Subsequence With the Minimum Score (Leetcode Hard)Programming Live with Larry · 42:50 · 616 views
2565. Subsequence With the Minimum Score | LeetCode Weekly 332 | C++Priyanshi Porwal · 10:01 · 587 views
Leetcode 2565 || subsequence with the minimum score || #Leetcode || Weekly Contest 332Code With U-DAY · 19:45 · 545 views
Leetcode 2565: Subsequence With the Minimum ScoreAlgorithms Casts · 25:42 · 382 views
The problem
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:
- Let
leftbe the minimum index among all removed characters. - Let
rightbe 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 <= 105sandtconsist of only lowercase English letters.
Approach overview
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 1: Two-Pointer Method
This approach uses two pointers to traverse the given strings `s` and `t`. It identifies potential subsequences by finding matching parts from the beginning and end of the strings. We compare the indices covered, which is the potential score of the operation, and keep track of the minimum score obtained. The two-pointer method is efficient because it allows us to process the sequences in linear time, taking advantage of relative order preservation of subsequences.
def min_subsequence_score(s, t):
slen, tlen = len(s), len(t)
prefix = [0] * (tlen + 1)
suffix = [slen] * (tlen + 1)
# Building prefix using two pointers
j = 0
for i in range(slen):
if j < tlen and s[i] == t[j]:
j += 1
prefix[j] = i + 1
# Building suffix using two pointers
j = tlen - 1
for i in range(slen - 1, -1, -1):
if j >= 0 and s[i] == t[j]:
j -= 1
suffix[j + 1] = i
# Calculate minimum score
min_score = slen
for i in range(tlen + 1):
min_score = min(min_score, suffix[i] - prefix[i] + 1)
return min_score
print(min_subsequence_score("abacaba", "bzaa")) # Output: 1
print(min_subsequence_score("cde", "xyz")) # Output: 3public class Solution {
public int minSubsequenceScore(String s, String t) {
int slen = s.length(), tlen = t.length();
int[] prefix = new int[tlen + 1];
int[] suffix = new int[tlen + 1];
for (int i = 0, j = 0; j < tlen; ++i) {
if (i < slen && s.charAt(i) == t.charAt(j)) j++;
prefix[j] = i+1;
}
for (int i = slen - 1, j = tlen - 1; j >= 0; --i) {
if (i >= 0 && s.charAt(i) == t.charAt(j)) j--;
suffix[j] = i;
}
int minScore = slen;
for (int i = 0; i <= tlen; ++i) {
minScore = Math.min(minScore, suffix[i] - prefix[i] + 1);
}
return minScore;
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.minSubsequenceScore("abacaba", "bzaa")); // Output: 1
System.out.println(sol.minSubsequenceScore("cde", "xyz")); // Output: 3
}
}#include <iostream>
#include <vector>
#include <string>
using namespace std;
int min_subsequence_score(string s, string t) {
int slen = s.length(), tlen = t.length();
vector<int> prefix(tlen + 1, 0), suffix(tlen + 1, slen);
for (int i = 0, j = 0; j < tlen; ++i) {
if (i < slen && s[i] == t[j]) j++;
prefix[j] = i+1;
}
for (int i = slen - 1, j = tlen - 1; j >= 0; --i) {
if (i >= 0 && s[i] == t[j]) j--;
suffix[j] = i;
}
int min_score = slen;
for (int i = 0; i <= tlen; ++i) {
min_score = min(min_score, suffix[i] - prefix[i] + 1);
}
return min_score;
}
int main() {
cout << min_subsequence_score("abacaba", "bzaa") << endl; // Output: 1
cout << min_subsequence_score("cde", "xyz") << endl; // Output: 3
return 0;
}function minSubsequenceScore(s, t) {
const slen = s.length, tlen = t.length;
const prefix = new Array(tlen + 1).fill(0);
const suffix = new Array(tlen + 1).fill(slen);
for (let i = 0, j = 0; j < tlen; ++i) {
if (i < slen && s[i] === t[j]) j++;
prefix[j] = i + 1;
}
for (let i = slen - 1, j = tlen - 1; j >= 0; --i) {
if (i >= 0 && s[i] === t[j]) j--;
suffix[j + 1] = i;
}
let minScore = slen;
for (let i = 0; i <= tlen; ++i) {
minScore = Math.min(minScore, suffix[i] - prefix[i] + 1);
}
return minScore;
}
console.log(minSubsequenceScore("abacaba", "bzaa")); // Output: 1
console.log(minSubsequenceScore("cde", "xyz")); // Output: 3;#include <stdio.h>
#include <string.h>
#define MIN(a, b) ((a) < (b) ? (a) : (b))
int min_subsequence_score(const char* s, const char* t) {
int slen = strlen(s), tlen = strlen(t);
int prefix[tlen + 1], suffix[tlen + 1];
// Initializing prefix and suffix
prefix[0] = suffix[tlen] = 0;
// Calculate left using prefix
for (int i = 0, j = 0; j < tlen; ++i) {
if (i < slen && s[i] == t[j]) j++;
prefix[j] = i+1;
}
// Calculate right using suffix
for (int i = slen - 1, j = tlen - 1; j >= 0; --i) {
if (i >= 0 && s[i] == t[j]) j--;
suffix[j] = i;
}
// Find minimum score
int min_score = slen;
for (int i = 0; i <= tlen; ++i) {
min_score = MIN(min_score, suffix[i] - prefix[i] + 1);
}
return min_score;
}
int main() {
printf("%d\n", min_subsequence_score("abacaba", "bzaa")); // Output: 1
printf("%d\n", min_subsequence_score("cde", "xyz")); // Output: 3
return 0;
}using System;
public class Solution {
public int MinSubsequenceScore(string s, string t) {
int slen = s.Length, tlen = t.Length;
int[] prefix = new int[tlen + 1];
int[] suffix = new int[tlen + 1];
for (int i = 0, j = 0; j < tlen; ++i) {
if (i < slen && s[i] == t[j]) j++;
prefix[j] = i + 1;
}
for (int i = slen - 1, j = tlen - 1; j >= 0; --i) {
if (i >= 0 && s[i] == t[j]) j--;
suffix[j + 1] = i;
}
int minScore = slen;
for (int i = 0; i <= tlen; ++i) {
minScore = Math.Min(minScore, suffix[i] - prefix[i] + 1);
}
return minScore;
}
public static void Main(string[] args) {
Solution sol = new Solution();
Console.WriteLine(sol.MinSubsequenceScore("abacaba", "bzaa")); // Output: 1
Console.WriteLine(sol.MinSubsequenceScore("cde", "xyz")); // Output: 3
}
}This Python function constructs prefix and suffix pointers, through which it identifies potential subsequences of `t` in `s`, with the goal of minimizing the index difference, and hence, the score.
Time Complexity: O(|s| + |t|)
Space Complexity: O(|t|)
Approach 2: Dynamic Programming Approach
This approach uses a dynamic programming table to store scores based on character positions. The idea is to find common subsequences by matching characters while filling a dp table. Though not as efficient as the two-pointer approach when implemented with basic traversal, it lays groundwork for more complex subsequence problems by tracking scores in a dp matrix.
def dp_min_subsequence_score(s, t):
slen, tlen = len(s), len(t)
dp = [tlen - j for j in range(tlen + 1)]
for i in range(slen - 1, -1, -1):
prev = tlen
for j in range(tlen - 1, -1, -1):
temp = dp[j]
dp[j] = dp[j + 1]
if s[i] == t[j]:
dp[j] = min(prev, dp[j])
prev = temp
return dp[0]
print(dp_min_subsequence_score("abacaba", "bzaa")) # Output: 1
print(dp_min_subsequence_score("cde", "xyz")) # Output: 3public class Solution {
public int dpMinSubsequenceScore(String s, String t) {
int slen = s.length(), tlen = t.length();
int[] dp = new int[tlen + 1];
for (int j = 0; j <= tlen; j++) {
dp[j] = tlen - j;
}
for (int i = slen - 1; i >= 0; i--) {
int prev = tlen;
for (int j = tlen - 1; j >= 0; j--) {
int temp = dp[j];
dp[j] = dp[j + 1];
if (s.charAt(i) == t.charAt(j)) {
dp[j] = Math.min(prev, dp[j]);
}
prev = temp;
}
}
return dp[0];
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.dpMinSubsequenceScore("abacaba", "bzaa")); // Output: 1
System.out.println(sol.dpMinSubsequenceScore("cde", "xyz")); // Output: 3
}
}#include <iostream>
#include <vector>
#include <string>
using namespace std;
int dp_minSubsequenceScore(string s, string t) {
int slen = s.length(), tlen = t.length();
vector<int> dp(tlen + 1, tlen);
for (int i = slen - 1; i >= 0; --i) {
int prev = tlen;
for (int j = tlen - 1; j >= 0; --j) {
int temp = dp[j];
dp[j] = dp[j + 1];
if (s[i] == t[j]) {
dp[j] = min(prev, dp[j]);
}
prev = temp;
}
}
return dp[0];
}
int main() {
cout << dp_minSubsequenceScore("abacaba", "bzaa") << endl; // Output: 1
cout << dp_minSubsequenceScore("cde", "xyz") << endl; // Output: 3
return 0;
}function dpMinSubsequenceScore(s, t) {
const slen = s.length, tlen = t.length;
const dp = new Array(tlen + 1).fill(0).map((_, j) => tlen - j);
for (let i = slen - 1; i >= 0; --i) {
let prev = tlen;
for (let j = tlen - 1; j >= 0; --j) {
const temp = dp[j];
dp[j] = dp[j + 1];
if (s[i] === t[j]) {
dp[j] = Math.min(prev, dp[j]);
}
prev = temp;
}
}
return dp[0];
}
console.log(dpMinSubsequenceScore("abacaba", "bzaa")); // Output: 1
console.log(dpMinSubsequenceScore("cde", "xyz")); // Output: 3;#include <stdio.h>
#include <string.h>
int min(int a, int b) {
return (a < b) ? a : b;
}
int dp_min_subsequence(const char *s, const char *t) {
int slen = strlen(s), tlen = strlen(t);
int dp[tlen + 1];
for (int j = 0; j <= tlen; ++j) {
dp[j] = tlen - j;
}
for (int i = slen - 1; i >= 0; --i) {
int prev = tlen;
for (int j = tlen - 1; j >= 0; --j) {
int temp = dp[j];
dp[j] = dp[j + 1];
if (s[i] == t[j]) {
dp[j] = min(prev, dp[j]);
}
prev = temp;
}
}
return dp[0];
}
int main() {
printf("%d\n", dp_min_subsequence("abacaba", "bzaa")); // Output: 1
printf("%d\n", dp_min_subsequence("cde", "xyz")); // Output: 3
return 0;
}using System;
public class Solution {
public int DpMinSubsequenceScore(string s, string t) {
int slen = s.Length, tlen = t.Length;
int[] dp = new int[tlen + 1];
for (int j = 0; j <= tlen; j++) {
dp[j] = tlen - j;
}
for (int i = slen - 1; i >= 0; i--) {
int prev = tlen;
for (int j = tlen - 1; j >= 0; j--) {
int temp = dp[j];
dp[j] = dp[j + 1];
if (s[i] == t[j]) {
dp[j] = Math.Min(prev, dp[j]);
}
prev = temp;
}
}
return dp[0];
}
public static void Main(string[] args) {
Solution sol = new Solution();
Console.WriteLine(sol.DpMinSubsequenceScore("abacaba", "bzaa")); // Output: 1
Console.WriteLine(sol.DpMinSubsequenceScore("cde", "xyz")); // Output: 3
}
}The dynamic programming technique keeps track of previous scores with an array, where each entry denotes the minimum score needed for a subsequence. This structure helps minimize the necessary costs to build `t` from `s`.
Time Complexity: O(|s| * |t|)
Space Complexity: O(|t|)
Approach 3: 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.
Therefore, we can preprocess to get arrays f and g, where f[i] represents the minimum number of characters in the prefix t[0,..i] of string t that match the first [0,..f[i]] characters of string s; similarly, g[i] represents the maximum number of characters in the suffix t[i,..n-1] of string t that match the last [g[i],..n-1] characters of string s.
The length of the deleted characters has monotonicity. If the condition is satisfied after deleting a string of length x, then the condition is definitely satisfied after deleting a string of length x+1. Therefore, we can use the method of binary search to find the smallest length that satisfies the condition.
The time complexity is O(n times log n), and the space complexity is O(n). Where n is the length of string t.
func minimumScore(s string, t string) int {
m, n := len(s), len(t)
f := make([]int, n)
g := make([]int, n)
for i := range f {
f[i] = 1 << 30
g[i] = -1
}
for i, j := 0, 0; i < m && j < n; i++ {
if s[i] == t[j] {
f[j] = i
j++
}
}
for i, j := m-1, n-1; i >= 0 && j >= 0; i-- {
if s[i] == t[j] {
g[j] = i
j--
}
}
return sort.Search(n+1, func(x int) bool {
for k := 0; k < n; k++ {
i, j := k-1, k+x
l, r := -1, m+1
if i >= 0 {
l = f[i]
}
if j < n {
r = g[j]
}
if l < r {
return true
}
}
return false
})
}Complexity comparison
| Approach | Complexity |
|---|---|
| Two-Pointer Method | Time Complexity: O(|s| + |t|) |
| Dynamic Programming Approach | Time Complexity: O(|s| * |t|) |
| Prefix and Suffix Preprocessing + Binary Search | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Subsequence With the Minimum Score easy or hard?
Subsequence With the Minimum Score is categorized as a Hard problem because it requires recognizing the prefix–suffix subsequence structure and converting that insight into a linear two-pointer algorithm. Many initial attempts use O(n * m) dynamic programming before discovering the optimized approach.
How to solve Subsequence With the Minimum Score in O(n)?
Use two passes over the strings. In the first pass, match characters of t inside s from left to right and store the earliest index in s for every prefix of t. In the second pass, match from right to left to record suffix positions. A two-pointer sweep across these arrays identifies the smallest gap between prefix and suffix matches, which gives the minimum removal length.
Subsequence With the Minimum Score Python or Java solution?
Both Python and Java implementations follow the same structure: compute prefix matches of t in s, compute suffix matches from the right, then use two pointers to minimize the removed substring length. The algorithm remains O(n + m) regardless of language and uses simple arrays or lists.
What is the best approach for Subsequence With the Minimum Score?
The most efficient solution uses a two-pointer technique with prefix and suffix subsequence matches. First compute where each prefix of t can appear in s, then compute where each suffix can appear from the right. By sliding two pointers across these arrays, you find the smallest middle substring to remove. This runs in O(n + m) time and O(m) space.
Is Subsequence With the Minimum Score asked at Google/Amazon/Meta?
Hard string and subsequence problems like this frequently appear in interviews at large tech companies including Google, Amazon, and Meta. The problem tests your ability to reason about subsequences, pointer movement, and optimizing from a naive dynamic programming approach to a linear scan.
What data structure is used in Subsequence With the Minimum Score?
The solution mainly uses arrays to store prefix and suffix match positions and applies a two-pointer traversal over them. The core techniques come from string processing and pointer manipulation rather than complex data structures.
What is the time complexity of Subsequence With the Minimum Score?
The optimal algorithm runs in O(n + m) time where n is the length of s and m is the length of t. It performs one forward scan and one backward scan to record subsequence matches, then a linear two-pointer pass to compute the minimum removal length. A dynamic programming formulation would take O(n * m) time.