Scale Engineer

Subsequence With the Minimum Score

Hard
#2345Time: O(m^2 * (n + m)), where `n` and `m` are the lengths of `s` and `t` respectively. There are `O(m^2)` pairs of `(i, j)`. For each, string concatenation takes `O(m)` and the subsequence check takes `O(n + m)`. This is prohibitively slow.Space: O(m), where `m` is the length of `t`. This is for storing the `remainingT` string in each iteration.1 company
Patterns
Two Pointers
Algorithms
Binary Search
Data structures
String
Companies
DoorDash

Prompt

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.

Approaches

3 approaches with complexity analysis and trade-offs.

The brute-force approach systematically explores every possible scenario. We can remove any contiguous subsegment of characters from t. The idea is to try removing every possible substring t[i...j], check if the remaining parts of t form a subsequence of s, and if they do, we consider the length of the removed substring as a potential answer. We keep track of the minimum length found so far.

Algorithm

  1. Initialize min_score to the length of t, m. This is the score if we remove the entire string t.
  2. Check if t is already a subsequence of s. If so, the score is 0, and we can return immediately.
  3. Iterate through all possible contiguous substrings t[i...j] to remove. This can be done with two nested loops:
    • The outer loop for the start index i from 0 to m.
    • The inner loop for the end index j from i to m.
  4. For each pair (i, j), we are considering removing the substring t[i...j-1]. The length of this removal is j - i.
  5. Construct the remaining string t_rem by concatenating the prefix t[0...i-1] and the suffix t[j...m-1].
  6. Check if t_rem is a subsequence of s using a helper function. This check can be done in O(s.length() + t_rem.length()) time with a two-pointer approach.
  7. If t_rem is a subsequence of s, update min_score = min(min_score, j - i).
  8. After checking all (i, j) pairs, min_score will hold the minimum possible score.

Walkthrough

This method iterates through all O(m^2) possible contiguous subsegments of t to remove. For each subsegment, defined by start and end indices i and j, we form a new string by taking t's prefix up to i and suffix from j. Then, we perform a subsequence check to see if this new string is a subsequence of s. The subsequence check itself takes time proportional to the lengths of the strings involved. The minimum length of a valid removal (j - i) is recorded. This process guarantees finding the minimum score but is computationally very expensive.

class Solution {    public int minimumScore(String s, String t) {        int m = t.length();        int n = s.length();        int minScore = m;         // Case: remove nothing        if (isSubsequence(s, t)) {            return 0;        }         // Iterate through all substrings t[i...j-1] to remove        for (int i = 0; i <= m; i++) {            for (int j = i; j <= m; j++) {                // Removed part is t[i...j-1]                String prefix = t.substring(0, i);                String suffix = t.substring(j);                String remainingT = prefix + suffix;                 if (isSubsequence(s, remainingT)) {                    minScore = Math.min(minScore, j - i);                }            }        }        return minScore;    }     private boolean isSubsequence(String s, String t) {        int i = 0, j = 0;        while (i < s.length() && j < t.length()) {            if (s.charAt(i) == t.charAt(j)) {                j++;            }            i++;        }        return j == t.length();    }}

Complexity

Time

O(m^2 * (n + m)), where `n` and `m` are the lengths of `s` and `t` respectively. There are `O(m^2)` pairs of `(i, j)`. For each, string concatenation takes `O(m)` and the subsequence check takes `O(n + m)`. This is prohibitively slow.

Space

O(m), where `m` is the length of `t`. This is for storing the `remainingT` string in each iteration.

Trade-offs

Pros

  • Simple to understand and implement.

  • Correctly solves the problem for small inputs.

Cons

  • Extremely inefficient due to the nested loops iterating through all possible substrings to remove.

  • The subsequence check is repeated for many overlapping subproblems.

  • Will result in a 'Time Limit Exceeded' error on platforms like LeetCode for the given constraints.

Solutions

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;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem