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

Algorithms

Data structures

Companies

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 <= 10⁵
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

Initialize min_score to the length of t, m. This is the score if we remove the entire string t.
Check if t is already a subsequence of s. If so, the score is 0, and we can return immediately.
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.
For each pair (i, j), we are considering removing the substring t[i...j-1]. The length of this removal is j - i.
Construct the remaining string t_rem by concatenating the prefix t[0...i-1] and the suffix t[j...m-1].
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.
If t_rem is a subsequence of s, update min_score = min(min_score, j - i).
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.

1class Solution {2    public int minimumScore(String s, String t) {3        int m = t.length();4        int n = s.length();5        int minScore = m;6 7        // Case: remove nothing8        if (isSubsequence(s, t)) {9            return 0;10        }11 12        // Iterate through all substrings t[i...j-1] to remove13        for (int i = 0; i <= m; i++) {14            for (int j = i; j <= m; j++) {15                // Removed part is t[i...j-1]16                String prefix = t.substring(0, i);17                String suffix = t.substring(j);18                String remainingT = prefix + suffix;19 20                if (isSubsequence(s, remainingT)) {21                    minScore = Math.min(minScore, j - i);22                }23            }24        }25        return minScore;26    }27 28    private boolean isSubsequence(String s, String t) {29        int i = 0, j = 0;30        while (i < s.length() && j < t.length()) {31            if (s.charAt(i) == t.charAt(j)) {32                j++;33            }34            i++;35        }36        return j == t.length();37    }38}

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.

A more optimized approach involves precomputation. The problem asks us to keep a prefix and a suffix of t. Let's say we keep prefix t[0...i-1] and suffix t[j...m-1]. For this to be a valid subsequence of s, the prefix must match some part of s that ends before the part where the suffix match begins. We can precompute the earliest possible end positions for all prefixes of t and the latest possible start positions for all suffixes of t. With this information, for each prefix, we can efficiently find the best suffix to pair it with.

Algorithm

Precomputation:
- Create an array prefixEnd of size m+1. prefixEnd[i] will store the minimum index k in s such that t[0...i-1] is a subsequence of s[0...k]. We can compute this in O(n+m) time using a two-pointer approach. If a prefix is not a subsequence of s, we store a sentinel value (e.g., n).
- Create an array suffixStart of size m+1. suffixStart[j] will store the maximum index k in s such that t[j...m-1] is a subsequence of s[k...n-1]. This can be computed similarly in O(n+m) by iterating from the ends of the strings. If a suffix is not a subsequence, we store a sentinel value (e.g., -1).
Finding the Minimum Score:
- Initialize minScore to m.
- Iterate with i from 0 to m, representing the length of the prefix t[0...i-1] that we keep.
- For each i, if prefixEnd[i] is valid (not the sentinel value), we need to find the longest possible suffix t[j...m-1] that can follow. This means finding the smallest j >= i.
- The condition for a valid combination of prefix t[0...i-1] and suffix t[j...m-1] is prefixEnd[i] < suffixStart[j].
- Since suffixStart is non-decreasing, for a fixed i, we can use binary search on the range [i, m] to find the smallest j that satisfies the condition.
- If such a j is found, the score is j - i. We update minScore = min(minScore, j - i).
- We also need to consider the case where we only keep the prefix, which means removing t[i...m-1]. The score is m-i. This is implicitly handled if the binary search returns j=m.
Return minScore.

Walkthrough

We can precompute two arrays. prefixEnd[i] stores the minimum ending index in s for the prefix t[0...i-1]. suffixStart[j] stores the maximum starting index in s for the suffix t[j...m-1]. Both arrays can be filled in O(n+m) time.

After precomputation, we iterate through each possible prefix length i from 0 to m. For each prefix t[0...i-1], we need to find the smallest j >= i such that prefixEnd[i] < suffixStart[j]. This condition ensures that the match for the prefix in s does not overlap with the match for the suffix. Since suffixStart is sorted (non-decreasing), we can use binary search to find this j for each i. The length of the removed part is j-i, and we minimize this value over all valid i.

1class Solution {2    public int minimumScore(String s, String t) {3        int n = s.length(), m = t.length();4 5        // prefixEnd[i]: min ending index in s for t's prefix of length i6        int[] prefixEnd = new int[m + 1];7        prefixEnd[0] = -1;8        int sPtr = 0;9        for (int i = 1; i <= m; i++) {10            char target = t.charAt(i - 1);11            while (sPtr < n && s.charAt(sPtr) != target) {12                sPtr++;13            }14            if (sPtr == n) {15                for (int k = i; k <= m; k++) prefixEnd[k] = n;16                break;17            }18            prefixEnd[i] = sPtr;19            sPtr++;20        }21 22        // suffixStart[j]: max starting index in s for t's suffix starting at j23        int[] suffixStart = new int[m + 1];24        suffixStart[m] = n;25        sPtr = n - 1;26        for (int j = m - 1; j >= 0; j--) {27            char target = t.charAt(j);28            while (sPtr >= 0 && s.charAt(sPtr) != target) {29                sPtr--;30            }31            if (sPtr < 0) {32                for (int k = j; k >= 0; k--) suffixStart[k] = -1;33                break;34            }35            suffixStart[j] = sPtr;36            sPtr--;37        }38 39        int minScore = m;40 41        // Find min score by combining prefixes and suffixes42        for (int i = 0; i <= m; i++) {43            if (prefixEnd[i] == n) { // Prefix t[0...i-1] doesn't exist in s44                minScore = Math.min(minScore, i); // Must remove at least this prefix45                break;46            }47            // Binary search for the smallest j >= i such that suffixStart[j] > prefixEnd[i]48            int low = i, high = m, j = m + 1;49            while(low <= high) {50                int mid = low + (high - low) / 2;51                if (suffixStart[mid] > prefixEnd[i]) {52                    j = mid;53                    high = mid - 1;54                } else {55                    low = mid + 1;56                }57            }58            minScore = Math.min(minScore, j - i);59        }60        return minScore;61    }62}

Complexity

Time

O(n + m log m). Precomputation takes `O(n+m)`. The main loop runs `m` times, with a binary search of `O(log m)` in each iteration.

Space

O(m) for the `prefixEnd` and `suffixStart` arrays.

Trade-offs

Pros

Significantly more efficient than the brute-force approach.
The precomputation step is linear and avoids redundant calculations.

Cons

Slightly more complex to implement than the brute-force approach.
Not the most optimal solution, as the binary search can be replaced by a more efficient two-pointer scan.

This approach optimizes the previous one by replacing the binary search with a more efficient two-pointer scan. After the same O(n+m) precomputation, we can find the minimum score in O(m) time. The key observation is that as we extend the prefix we keep (by incrementing i), the earliest position its match can end in s (prefixEnd[i]) is non-decreasing. Consequently, the starting position of the suffix we need (suffixStart[j]) must also be further along. This monotonicity allows us to use a second pointer j that only moves forward, avoiding the repeated logarithmic-time searches.

Algorithm

Precomputation: This step is identical to the previous approach. We compute the prefixEnd and suffixStart arrays in O(n+m) time.
Finding the Minimum Score with Two Pointers:
- Initialize minScore to m.
- Initialize a pointer j = 0 for the suffixStart array.
- Iterate with a pointer i from 0 to m (for each prefix t[0...i-1]):
  - First, check if the prefix t[0...i-1] is valid. If prefixEnd[i] is the sentinel value n, it means this prefix (and any longer ones) cannot be formed. We can break the loop.
  - We need to find the smallest j >= i such that prefixEnd[i] < suffixStart[j]. We can use the j pointer for this.
  - Since i is increasing, prefixEnd[i] is non-decreasing. This means the required j will also be non-decreasing. So, we don't need to reset j for each i.
  - Advance the j pointer: while (j <= m && (j < i || prefixEnd[i] >= suffixStart[j])) { j++; }.
  - This loop finds the smallest j that is at least i and satisfies the condition prefixEnd[i] < suffixStart[j].
  - If j <= m, we have a valid split. The score is j - i. Update minScore = min(minScore, j - i).
  - If j goes beyond m, it means for the current prefix, no suffix can be appended. The only option is to remove the rest of t, i.e., t[i...m-1]. The score is m-i. This case is also implicitly handled by the logic.
Return minScore.

Walkthrough

The precomputation of prefixEnd and suffixStart arrays remains the same. The improvement lies in how we find the optimal split. We use two pointers, i and j. i iterates from 0 to m, representing the length of the prefix t[0...i-1] to be kept. j points to the start of the suffix t[j...m-1] to be kept.

For each i, we need the smallest j >= i such that prefixEnd[i] < suffixStart[j]. Since prefixEnd[i] is non-decreasing with i, the valid j for i+1 will be greater than or equal to the valid j for i. This allows us to use a single pass for both pointers. The j pointer never needs to move backward. This amortizes the search for j over all i, leading to a linear time complexity for this part of the algorithm.

1class Solution {2    public int minimumScore(String s, String t) {3        int n = s.length(), m = t.length();4 5        int[] prefixEnd = new int[m + 1];6        prefixEnd[0] = -1;7        int sPtr = 0;8        for (int i = 1; i <= m; i++) {9            char target = t.charAt(i - 1);10            while (sPtr < n && s.charAt(sPtr) != target) {11                sPtr++;12            }13            if (sPtr == n) {14                for (int k = i; k <= m; k++) prefixEnd[k] = n;15                break;16            }17            prefixEnd[i] = sPtr;18            sPtr++;19        }20 21        int[] suffixStart = new int[m + 1];22        suffixStart[m] = n;23        sPtr = n - 1;24        for (int j = m - 1; j >= 0; j--) {25            char target = t.charAt(j);26            while (sPtr >= 0 && s.charAt(sPtr) != target) {27                sPtr--;28            }29            if (sPtr < 0) {30                for (int k = j; k >= 0; k--) suffixStart[k] = -1;31                break;32            }33            suffixStart[j] = sPtr;34            sPtr--;35        }36 37        int minScore = m;38        int j = 0;39        for (int i = 0; i <= m; i++) {40            // Find smallest j >= i such that prefixEnd[i] < suffixStart[j]41            while (j <= m && (j < i || prefixEnd[i] >= suffixStart[j])) {42                j++;43            }44            if (j > m) { // No valid suffix can be appended45                 // Only option is to remove t[i...m-1]46                 minScore = Math.min(minScore, m - i);47                 break; // No longer prefixes can be formed either48            }49            minScore = Math.min(minScore, j - i);50        }51        return minScore;52    }53}

Complexity

Time

O(n + m). Precomputation takes `O(n+m)`. The two-pointer scan to find the minimum score takes `O(m)` because both pointers `i` and `j` only move forward through the arrays. This gives a total linear time complexity.

Space

O(m) for the `prefixEnd` and `suffixStart` arrays.

Trade-offs

Pros

This is the most efficient solution with optimal time complexity.
It solves the problem in a single pass after precomputation.

Cons

The two-pointer logic can be tricky to get right compared to the more straightforward binary search.

Solutions

Solution

1class Solution {2private3  int m;4private5  int n;6private7  int[] f;8private9  int[] g;10public11  int minimumScore(String s, String t) {12    m = s.length();13    n = t.length();14    f = new int[n];15    g = new int[n];16    for (int i = 0; i < n; ++i) {17      f[i] = 1 << 30;18      g[i] = -1;19    }20    for (int i = 0, j = 0; i < m && j < n; ++i) {21      if (s.charAt(i) == t.charAt(j)) {22        f[j] = i;23        ++j;24      }25    }26    for (int i = m - 1, j = n - 1; i >= 0 && j >= 0; --i) {27      if (s.charAt(i) == t.charAt(j)) {28        g[j] = i;29        --j;30      }31    }32    int l = 0, r = n;33    while (l < r) {34      int mid = (l + r) >> 1;35      if (check(mid)) {36        r = mid;37      } else {38        l = mid + 1;39      }40    }41    return l;42  }43private44  boolean check(int len) {45    for (int k = 0; k < n; ++k) {46      int i = k - 1, j = k + len;47      int l = i >= 0 ? f[i] : -1;48      int r = j < n ? g[j] : m + 1;49      if (l < r) {50        return true;51      }52    }53    return false;54  }55}

1class Solution {2public:3  int minimumScore(string s, string t) {4    int m = s.size(), n = t.size();5    vector<int> f(n, 1e6);6    vector<int> g(n, -1);7    for (int i = 0, j = 0; i < m && j < n; ++i) {8      if (s[i] == t[j]) {9        f[j] = i;10        ++j;11      }12    }13    for (int i = m - 1, j = n - 1; i >= 0 && j >= 0; --i) {14      if (s[i] == t[j]) {15        g[j] = i;16        --j;17      }18    }19    auto check = [&](int len) {20      for (int k = 0; k < n; ++k) {21        int i = k - 1, j = k + len;22        int l = i >= 0 ? f[i] : -1;23        int r = j < n ? g[j] : m + 1;24        if (l < r) {25          return true;26        }27      }28      return false;29    };30    int l = 0, r = n;31    while (l < r) {32      int mid = (l + r) >> 1;33      if (check(mid)) {34        r = mid;35      } else {36        l = mid + 1;37      }38    }39    return l;40  }41};

1class Solution:2    def minimumScore(self, s: str, t: str) -> int: def check(x): for k in range(n): i, j = k - 1, k + x l = f[i] if i >= 0 else - 1 r = g[j] if j < n else m + 1 if l < r: return True return False m, n = len(s), len(t) f = [inf] * n g = [- 1] * n i, j = 0, 0 while i < m and j < n: if s[i] == t[j]: f[j] = i j += 1 i += 1 i, j = m - 1, n - 1 while i >= 0 and j >= 0: if s[i] == t[j]: g[j] = i j -= 1 i -= 1 return bisect_left(range(n + 1), True, key=check)

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 problem

Solution

1class Solution {2private3  int m;4private5  int n;6private7  int[] f;8private9  int[] g;10public11  int minimumScore(String s, String t) {12    m = s.length();13    n = t.length();14    f = new int[n];15    g = new int[n];16    for (int i = 0; i < n; ++i) {17      f[i] = 1 << 30;18      g[i] = -1;19    }20    for (int i = 0, j = 0; i < m && j < n; ++i) {21      if (s.charAt(i) == t.charAt(j)) {22        f[j] = i;23        ++j;24      }25    }26    for (int i = m - 1, j = n - 1; i >= 0 && j >= 0; --i) {27      if (s.charAt(i) == t.charAt(j)) {28        g[j] = i;29        --j;30      }31    }32    int l = 0, r = n;33    while (l < r) {34      int mid = (l + r) >> 1;35      if (check(mid)) {36        r = mid;37      } else {38        l = mid + 1;39      }40    }41    return l;42  }43private44  boolean check(int len) {45    for (int k = 0; k < n; ++k) {46      int i = k - 1, j = k + len;47      int l = i >= 0 ? f[i] : -1;48      int r = j < n ? g[j] : m + 1;49      if (l < r) {50        return true;51      }52    }53    return false;54  }55}

1class Solution {2public:3  int minimumScore(string s, string t) {4    int m = s.size(), n = t.size();5    vector<int> f(n, 1e6);6    vector<int> g(n, -1);7    for (int i = 0, j = 0; i < m && j < n; ++i) {8      if (s[i] == t[j]) {9        f[j] = i;10        ++j;11      }12    }13    for (int i = m - 1, j = n - 1; i >= 0 && j >= 0; --i) {14      if (s[i] == t[j]) {15        g[j] = i;16        --j;17      }18    }19    auto check = [&](int len) {20      for (int k = 0; k < n; ++k) {21        int i = k - 1, j = k + len;22        int l = i >= 0 ? f[i] : -1;23        int r = j < n ? g[j] : m + 1;24        if (l < r) {25          return true;26        }27      }28      return false;29    };30    int l = 0, r = n;31    while (l < r) {32      int mid = (l + r) >> 1;33      if (check(mid)) {34        r = mid;35      } else {36        l = mid + 1;37      }38    }39    return l;40  }41};

1class Solution:2    def minimumScore(self, s: str, t: str) -> int: def check(x): for k in range(n): i, j = k - 1, k + x l = f[i] if i >= 0 else - 1 r = g[j] if j < n else m + 1 if l < r: return True return False m, n = len(s), len(t) f = [inf] * n g = [- 1] * n i, j = 0, 0 while i < m and j < n: if s[i] == t[j]: f[j] = i j += 1 i += 1 i, j = m - 1, n - 1 while i >= 0 and j >= 0: if s[i] == t[j]: g[j] = i j -= 1 i -= 1 return bisect_left(range(n + 1), True, key=check)

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.