LeetCode 2565. Subsequence With the Minimum Score Solution in Java, C++, Python & Go | Explanation + Code

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 1: Prefix and Suffix Preprocessing + Binary Search

According to the problem, we know that the range of the index to delete characters is [left, right]. The optimal approach is to delete all characters within the range [left, right]. In other words, we need to delete a substring from string t, so that the remaining prefix of string t can match the prefix of string s, and the remaining suffix of string t can match the suffix of string s, and the prefix and suffix of string s do not overlap. Note that the match here refers to subsequence matching.

Therefore, we can preprocess to get arrays f and g, where f[i] represents the minimum number of characters in the prefix t[0,..i] of string t that match the first [0,..f[i]] characters of string s; similarly, g[i] represents the maximum number of characters in the suffix t[i,..n-1] of string t that match the last [g[i],..n-1] characters of string s.

The length of the deleted characters has monotonicity. If the condition is satisfied after deleting a string of length x, then the condition is definitely satisfied after deleting a string of length x+1. Therefore, we can use the method of binary search to find the smallest length that satisfies the condition.

The time complexity is O(n × log n), and the space complexity is O(n). Where n is the length of string t.

PythonJavaC++Go

class Solution: 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)(code-box)

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; } }(code-box)

class Solution { public: int minimumScore(string s, string t) { int m = s.size(), n = t.size(); vector<int> f(n, 1e6); vector<int> g(n, -1); for (int i = 0, j = 0; i < m && j < n; ++i) { if (s[i] == t[j]) { f[j] = i; ++j; } } for (int i = m - 1, j = n - 1; i >= 0 && j >= 0; --i) { if (s[i] == t[j]) { g[j] = i; --j; } } auto 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; }; int l = 0, r = n; while (l < r) { int mid = (l + r) >> 1; if (check(mid)) { r = mid; } else { l = mid + 1; } } return l; } };(code-box)

func minimumScore(s string, t string) int { m, n := len(s), len(t) f := make([]int, n) g := make([]int, n) for i := range f { f[i] = 1 << 30 g[i] = -1 } for i, j := 0, 0; i < m && j < n; i++ { if s[i] == t[j] { f[j] = i j++ } } for i, j := m-1, n-1; i >= 0 && j >= 0; i-- { if s[i] == t[j] { g[j] = i j-- } } return sort.Search(n+1, func(x int) bool { for k := 0; k < n; k++ { i, j := k-1, k+x l, r := -1, m+1 if i >= 0 { l = f[i] } if j < n { r = g[j] } if l < r { return true } } return false }) }(code-box)