2565. Subsequence With the Minimum Score LeetCode Solution

Last updated: March 5, 2025

In this guide, you will get 2565. Subsequence With the Minimum Score LeetCode Solution with the best time and space complexity. The solution to Subsequence With the Minimum Score problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Subsequence With the Minimum Score solution in C++
Subsequence With the Minimum Score solution in Java
Subsequence With the Minimum Score solution in Python
Additional Resources

2565. Subsequence With the Minimum Score LeetCode Solution image

Problem Statement of Subsequence With the Minimum Score

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 left be the minimum index among all removed characters.
Let 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 <= 105
s and t consist of only lowercase English letters.

Complexity Analysis

Time Complexity: O(|\texttt{s}| + |\texttt{t}|)
Space Complexity: O(|\texttt{s}|)

2565. Subsequence With the Minimum Score LeetCode Solution in C++

class Solution:
  def minimumScore(self, s: str, t: str) -> int:
    # leftmost[j] := the minimum index i s.t. t[0..j] is a subsequence of s[0..i].
    #          -1 := impossible
    leftmost = [-1] * len(t)
    # rightmost[j] := the maximum index i s.t. t[j:] is a subsequence of s[i..n).
    #           -1 := impossible
    rightmost = [-1] * len(t)

    j = 0  # t's index
    for i in range(len(s)):
      if s[i] == t[j]:
        leftmost[j] = i
        j += 1
        if j == len(t):
          break

    j = len(t) - 1  # t's index
    for i in reversed(range(len(s))):
      if s[i] == t[j]:
        rightmost[j] = i
        j -= 1
        if j == -1:
          break

    # The worst case is to delete t[0:j] since t[j:] is a subsequence of s. (deduced
    # from the above loop).
    ans = j + 1

    j = 0
    for i in range(len(t)):
      # It's impossible that t[0..i] is a subsequence of s. So, stop the loop since
      # no need to consider any larger i.
      if leftmost[i] == -1:
        break
      # While t[0..i] + t[j:] is not a subsequence of s, increase j.
      while j < len(t) and leftmost[i] >= rightmost[j]:
        j += 1
      # Now, leftmost[i] < rightmost[j], so t[0..i] + t[j:n] is a subsequence of s.
      # If i == j that means t is a subsequence of s, so just return 0.
      if i == j:
        return 0
      # Delete t[i + 1..j - 1] and that's a total of j - i - 1 letters.
      ans = min(ans, j - i - 1)

    return ans
/* code provided by PROGIEZ */

2565. Subsequence With the Minimum Score LeetCode Solution in Java

N/A
// code provided by PROGIEZ

2565. Subsequence With the Minimum Score LeetCode Solution in Python

N/A
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents