LeetCode #2565 — HARD

Subsequence With the Minimum Score

Break down a hard problem into reliable checkpoints, edge-case handling, and complexity trade-offs.

Solve on LeetCode
The Problem

Problem Statement

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.
Patterns Used
👉Two Pointers→🔍Modified Binary Search→

Roadmap

  1. Brute Force Baseline
  2. Core Insight
  3. Algorithm Walkthrough
  4. Edge Cases
  5. Full Annotated Code
  6. Interactive Study Demo
  7. Complexity Analysis
Step 01

Brute Force Baseline

Problem summary: 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).

Baseline thinking

Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.

Pattern signal: Two Pointers · Binary Search

Example 1

"abacaba"
"bzaa"

Example 2

"cde"
"xyz"

Related Problems

  • Longest Common Subsequence (longest-common-subsequence)
Step 02

Core Insight

What unlocks the optimal approach

  • Maintain two pointers: i and j. We need to perform a similar operation: while t[0:i] + t[j:n] is not a subsequence of the string s, increase j.
  • We can check the condition greedily. Create the array leftmost[i] which denotes minimum index k, such that in prefix s[0:k] exists subsequence t[0:i]. Similarly, we define rightmost[i].
  • If leftmost[i] < rightmost[j] then t[0:i] + t[j:n] is the subsequence of s.
Interview move: turn each hint into an invariant you can check after every iteration/recursion step.
Step 03

Algorithm Walkthrough

Iteration Checklist

  1. Define state (indices, window, stack, map, DP cell, or recursion frame).
  2. Apply one transition step and update the invariant.
  3. Record answer candidate when condition is met.
  4. Continue until all input is consumed.
Use the first example testcase as your mental trace to verify each transition.
Step 04

Edge Cases

Minimum Input
Single element / shortest valid input
Validate boundary behavior before entering the main loop or recursion.
Duplicates & Repeats
Repeated values / repeated states
Decide whether duplicates should be merged, skipped, or counted explicitly.
Extreme Constraints
Largest constraint values
Re-check complexity target against constraints to avoid time-limit issues.
Invalid / Corner Shape
Empty collections, zeros, or disconnected structures
Handle special-case structure before the core algorithm path.
Step 05

Full Annotated Code

Source-backed implementations are provided below for direct study and interview prep.

// Accepted solution for LeetCode #2565: Subsequence With the Minimum Score
class Solution {
    private int m;
    private int n;
    private int[] f;
    private int[] g;

    public int minimumScore(String s, String t) {
        m = s.length();
        n = t.length();
        f = new int[n];
        g = new int[n];
        for (int i = 0; i < n; ++i) {
            f[i] = 1 << 30;
            g[i] = -1;
        }
        for (int i = 0, j = 0; i < m && j < n; ++i) {
            if (s.charAt(i) == t.charAt(j)) {
                f[j] = i;
                ++j;
            }
        }
        for (int i = m - 1, j = n - 1; i >= 0 && j >= 0; --i) {
            if (s.charAt(i) == t.charAt(j)) {
                g[j] = i;
                --j;
            }
        }
        int l = 0, r = n;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (check(mid)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }

    private boolean check(int len) {
        for (int k = 0; k < n; ++k) {
            int i = k - 1, j = k + len;
            int l = i >= 0 ? f[i] : -1;
            int r = j < n ? g[j] : m + 1;
            if (l < r) {
                return true;
            }
        }
        return false;
    }
}
Step 06

Interactive Study Demo

Use this to step through a reusable interview workflow for this problem.

Press Step or Run All to begin.
Step 07

Complexity Analysis

Time
O(n × log n)
Space
O(n)

Approach Breakdown

BRUTE FORCE
O(n²) time
O(1) space

Two nested loops check every pair of elements. The outer loop picks one element, the inner loop scans the rest. For n elements that is n × (n−1)/2 comparisons = O(n²). No extra memory — just two loop variables.

TWO POINTERS
O(n) time
O(1) space

Each pointer traverses the array at most once. With two pointers moving inward (or both moving right), the total number of steps is bounded by n. Each comparison is O(1), giving O(n) overall. No auxiliary data structures are needed — just two index variables.

Shortcut: Two converging pointers on sorted data → O(n) time, O(1) space.
Coach Notes

Common Mistakes

Review these before coding to avoid predictable interview regressions.

Moving both pointers on every comparison

Wrong move: Advancing both pointers shrinks the search space too aggressively and skips candidates.

Usually fails on: A valid pair can be skipped when only one side should move.

Fix: Move exactly one pointer per decision branch based on invariant.

Boundary update without `+1` / `-1`

Wrong move: Setting `lo = mid` or `hi = mid` can stall and create an infinite loop.

Usually fails on: Two-element ranges never converge.

Fix: Use `lo = mid + 1` or `hi = mid - 1` where appropriate.

Related Problems
#167Two Sum II - Input Array Is Sortedmedium→#287Find the Duplicate Numbermedium→#349Intersection of Two Arrayseasy→#350Intersection of Two Arrays IIeasy→#475Heatersmedium→