2565. Subsequence With the Minimum Score

Description

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.

 

Solutions

Solution: Two Pointers + Prefix Sum

• Time complexity: O(m+n)
• Space complexity: O(m)

 

JavaScript

/**
 * @param {string} s
 * @param {string} t
 * @return {number}
 */
const minimumScore = function (s, t) {
  const m = s.length;
  const n = t.length;
  const prefixSum = Array.from({ length: m }, () => 0);
  const suffixSum = Array.from({ length: m }, () => 0);
  let j = 0;

  for (let index = 0; index < m; index++) {
    if (s[index] === t[j]) {
      prefixSum[index] += 1;
      j += 1;
    }

    prefixSum[index] += prefixSum[index - 1] ?? 0;
  }

  j = n - 1;

  for (let index = m - 1; index >= 0; index--) {
    if (s[index] === t[j]) {
      suffixSum[index] += 1;
      j -= 1;
    }

    suffixSum[index] += suffixSum[index + 1] ?? 0;
  }

  let result = n - Math.max(prefixSum[m - 1], suffixSum[0]);

  for (let index = 0; index < m - 1; index++) {
    const score = n - prefixSum[index] - suffixSum[index + 1];

    result = Math.min(score, result);
  }

  return Math.max(result, 0);
};