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 maket _ 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 "_a_ b _c_ d _e_ " while "aec" is not).
Input: s ="abacaba", t ="bzaa"Output: 1Explanation: 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 is1-1+1=1.It can be proven that 1is the minimum score that we can achieve.
Input: s ="cde", t ="xyz"Output: 3Explanation: 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 is2-0+1=3.It can be proven that 3is the minimum score that we can achieve.
Precompute where each prefix of t can be matched in s (left-most positions) and where each suffix of t can be matched in s (right-most positions). Deleting a contiguous block t[l..r] is possible iff the prefix t[0..l-1] appears in s strictly before the suffix t[r+1..m-1]. Using the two position arrays we can binary-search the minimal suffix start that stays after a given prefix match.
Let m = len(t). Build left[0..m-1] where left[i] is the smallest index in s where t[0..i] is a subsequence (or INF if impossible).
Build right[0..m-1] where right[i] is the largest index in s where t[i..m-1] is a subsequence (or -INF if impossible).
Extend right with right[m] = +INF and left with a virtual left[-1] = -1 to simplify boundaries.
For each l from 0..m (delete starting at l), binary-search the smallest k >= l such that right[k] > left[l-1]. Then the deleted length is k - l. Track the minimum.
Edge cases: if t is already a subsequence of s then answer is 0; if no part can be matched then answer is m.
classSolution {
public:int minimumScore(string s, string t) {
int n = s.size(), m = t.size();
constint INF =1e9;
vector<int> left(m, INF), right(m, -INF);
// build left
int p =0;
for (int i =0; i < n && p < m; ++i) if (s[i] == t[p]) left[p++] = i;
for (int i =1; i < m; ++i) if (left[i] == INF) left[i] = left[i-1] == INF ? INF : left[i];
// build right
p = m -1;
for (int i = n-1; i >=0&& p >=0; --i) if (s[i] == t[p]) right[p--] = i;
// prepare R array of size m+1 where R[m] = INF
vector<int> R(m+1);
for (int i =0; i < m; ++i) R[i] = right[i];
R[m] = INF;
int ans = m;
// Lprev: left index for prefix length l-1; for l=0 use -1
for (int l =0; l <= m; ++l) {
int left_idx = (l ==0) ?-1: left[l-1];
// binary search smallest k in [l..m] with R[k] > left_idx
int lo = l, hi = m, pos = m+1;
while (lo <= hi) {
int mid = (lo + hi) >>1;
if (R[mid] > left_idx) { pos = mid; hi = mid -1; }
else lo = mid +1;
}
if (pos <= m) ans = min(ans, pos - l);
}
return ans;
}
};
classSolution {
publicintminimumScore(String s, String t) {
int n = s.length(), m = t.length();
finalint INF = 1_000_000_000;
int[] left =newint[m]; Arrays.fill(left, INF);
int[] right =newint[m]; Arrays.fill(right, -INF);
int p = 0;
for (int i = 0; i < n && p < m; ++i) if (s.charAt(i) == t.charAt(p)) left[p++]= i;
p = m - 1;
for (int i = n-1; i >= 0 && p >= 0; --i) if (s.charAt(i) == t.charAt(p)) right[p--]= i;
int[] R =newint[m+1];
for (int i = 0; i < m; ++i) R[i]= right[i];
R[m]= INF;
int ans = m;
for (int l = 0; l <= m; ++l) {
int leftIdx = (l == 0) ?-1 : left[l-1];
int lo = l, hi = m, pos = m+1;
while (lo <= hi) {
int mid = (lo + hi) >>> 1;
if (R[mid]> leftIdx) { pos = mid; hi = mid - 1; }
else lo = mid + 1;
}
if (pos <= m) ans = Math.min(ans, pos - l);
}
return ans;
}
}
classSolution {
funminimumScore(s: String, t: String): Int {
val n = s.length; val m = t.length
val INF = 1_000_000_000
val left = IntArray(m) { INF }
val right = IntArray(m) { -INF }
var p = 0for (i in0 until n) if (p < m && s[i] == t[p]) left[p++] = i
p = m - 1for (i in n-1 downTo 0) if (p >=0&& s[i] == t[p]) right[p--] = i
val R = IntArray(m+1)
for (i in0 until m) R[i] = right[i]
R[m] = INF
var ans = m
for (l in0..m) {
val leftIdx = if (l ==0) -1else left[l-1]
var lo = l; var hi = m; var pos = m+1while (lo <= hi) {
val mid = (lo + hi) ushr 1if (R[mid] > leftIdx) { pos = mid; hi = mid - 1 } else lo = mid + 1 }
if (pos <= m) ans = minOf(ans, pos - l)
}
return ans
}
}
classSolution:
defminimumScore(self, s: str, t: str) -> int:
n, m = len(s), len(t)
INF =10**9 left = [INF] * m
right = [-INF] * m
p =0for i, ch in enumerate(s):
if p < m and ch == t[p]:
left[p] = i
p +=1 p = m -1for i in range(n-1, -1, -1):
if p >=0and s[i] == t[p]:
right[p] = i
p -=1 R = right + [INF]
ans = m
# helper binary search over Rdefbs(lo: int, hi: int, target: int) -> int:
pos = hi +1while lo <= hi:
mid = (lo + hi) //2if R[mid] > target:
pos = mid
hi = mid -1else:
lo = mid +1return pos
for l in range(0, m+1):
left_idx =-1if l ==0else left[l-1]
k = bs(l, m, left_idx)
if k <= m:
ans = min(ans, k - l)
return ans
impl Solution {
pubfnminimum_score(s: String, t: String) -> i32 {
let n = s.len(); let m = t.len();
let s: Vec<char>= s.chars().collect();
let t: Vec<char>= t.chars().collect();
let inf =1_000_000_000i32;
letmut left =vec![inf; m];
letmut right =vec![-inf; m];
letmut p =0usize;
for i in0..n {
if p < m && s[i] == t[p] { left[p] = i asi32; p +=1 }
}
if m ==0 { return0 }
p = m -1;
for i in (0..n).rev() {
if p < m && s[i] == t[p] { right[p] = i asi32; if p==0 { break } else { p -=1 } }
}
letmut R: Vec<i32>= right.clone(); R.push(inf);
letmut ans = m asi32;
for l in0..=m {
let left_idx =if l==0 { -1 } else { left[l-1] };
// binary search
letmut lo = l; letmut hi = m; letmut pos = (m+1) asusize;
while lo <= hi {
let mid = (lo + hi) /2;
if R[mid] > left_idx { pos = mid; if mid==0 { break } else { hi = mid -1 } } else { lo = mid +1 }
}
if pos <= m { ans = ans.min((pos - l) asi32) }
}
ans
}
}
⏰ Time complexity: O(n + m log m) — building the left/right arrays costs O(n + m) and binary-searching for each prefix adds O(m log m) in the worst case.
🧺 Space complexity: O(m) — we store the two position arrays of length m.
Instead of binary-searching each prefix, walk the string s once to record earliest matches for prefixes and latest matches for suffixes, then use two pointers on the right array to find valid suffix starts for increasing prefixes in linear time.
classSolution {
publicintminimumScore(String s, String t) {
int n = s.length(), m = t.length();
finalint INF = 1_000_000_000;
int[] left =newint[m]; Arrays.fill(left, INF);
int[] right =newint[m]; Arrays.fill(right, -INF);
int p = 0;
for (int i = 0; i < n && p < m; ++i) if (s.charAt(i) == t.charAt(p)) left[p++]= i;
p = m-1;
for (int i = n-1; i >= 0 && p >= 0; --i) if (s.charAt(i) == t.charAt(p)) right[p--]= i;
int[] R =newint[m+1]; System.arraycopy(right, 0, R, 0, m); R[m]= INF;
int ans = m; int k = 0;
for (int l = 0; l <= m; ++l) {
int leftIdx = (l == 0) ?-1 : left[l-1];
while (k <= m && R[k]<= leftIdx) ++k;
if (k <= m) ans = Math.min(ans, k - l);
}
return ans;
}
}
classSolution:
defminimumScore(self, s: str, t: str) -> int:
n, m = len(s), len(t)
INF =10**9 left = [INF] * m
right = [-INF] * m
p =0for i, ch in enumerate(s):
if p < m and ch == t[p]:
left[p] = i; p +=1 p = m -1for i in range(n-1, -1, -1):
if p >=0and s[i] == t[p]:
right[p] = i; p -=1 R = right + [INF]
ans = m
k =0for l in range(0, m+1):
left_idx =-1if l ==0else left[l-1]
while k <= m and R[k] <= left_idx:
k +=1if k <= m:
ans = min(ans, k - l)
return ans