<p>You are given two strings <code>s</code> and <code>t</code>.</p>

<p>You are allowed to remove any number of characters from the string <code>t</code>.</p>

<p>The score of the string is <code>0</code> if no characters are removed from the string <code>t</code>, otherwise:</p>

<ul>
	<li>Let <code>left</code> be the minimum index among all removed characters.</li>
	<li>Let <code>right</code> be the maximum index among all removed characters.</li>
</ul>

<p>Then the score of the string is <code>right - left + 1</code>.</p>

<p>Return <em>the minimum possible score to make </em><code>t</code><em>&nbsp;a subsequence of </em><code>s</code><em>.</em></p>

<p>A <strong>subsequence</strong> 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., <code>&quot;ace&quot;</code> is a subsequence of <code>&quot;<u>a</u>b<u>c</u>d<u>e</u>&quot;</code> while <code>&quot;aec&quot;</code> is not).</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;abacaba&quot;, t = &quot;bzaa&quot;
<strong>Output:</strong> 1
<strong>Explanation:</strong> In this example, we remove the character &quot;z&quot; at index 1 (0-indexed).
The string t becomes &quot;baa&quot; which is a subsequence of the string &quot;abacaba&quot; and the score is 1 - 1 + 1 = 1.
It can be proven that 1 is the minimum score that we can achieve.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;cde&quot;, t = &quot;xyz&quot;
<strong>Output:</strong> 3
<strong>Explanation:</strong> In this example, we remove characters &quot;x&quot;, &quot;y&quot; and &quot;z&quot; at indices 0, 1, and 2 (0-indexed).
The string t becomes &quot;&quot; which is a subsequence of the string &quot;cde&quot; and the score is 2 - 0 + 1 = 3.
It can be proven that 3 is the minimum score that we can achieve.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= s.length, t.length &lt;= 10<sup>5</sup></code></li>
	<li><code>s</code> and <code>t</code> consist of only lowercase English letters.</li>
</ul>

class Solution:
    def minimumScore(self, s: str, t: str) -> int:
        # 9/8/2024
        # Helper function to check if there is a subsequence of length 'length'
        # within source that matches target.
        def is_match_possible(length):
            for start_index in range(source_length):
                prev_index = start_index - 1
                next_index = start_index + length
                left_bound = prefix_matches[prev_index] if prev_index >= 0 else -1
                right_bound = suffix_matches[next_index] if next_index < source_length else source_matches + 1
                if left_bound < right_bound:
                    return True
            return False

        source_matches, source_length = len(s), len(t)
        # Arrays to store the first and last match indices for each character in 'target'
        prefix_matches = [inf] * source_length
        suffix_matches = [-1] * source_length

        # Forward pass to populate prefix matches of target in source
        source_index, target_index = 0, 0
        while source_index < source_matches and target_index < source_length:
            if s[source_index] == t[target_index]:
                prefix_matches[target_index] = source_index
                target_index += 1
            source_index += 1

        # Backward pass to populate suffix matches of target in source
        source_index, target_index = source_matches - 1, source_length - 1
        while source_index >= 0 and target_index >= 0:
            if s[source_index] == t[target_index]:
                suffix_matches[target_index] = source_index
                target_index -= 1
            source_index -= 1

        # Using binary search to find the minimum length of subsequence
        # required such that 'target' is a subsequence of 'source'.
        # The search range is from 0 to 'source_length' + 1.
        return bisect_left(range(source_length + 1), True, key=is_match_possible)


        # n, m = len(s), len(t)
    
        # # Step 1: Compute prefix matching from left to right
        # left = [-1] * m  # left[i] means the largest index in s that can match t[0:i]
        # j = 0
        # for i in range(m):
        #    while j < n and s[j] != t[i]:
        #        j += 1
        #    if j < n:
        #        left[i] = j
        #        j += 1
    
        # # Step 2: Compute suffix matching from right to left
        # right = [-1] * m  # right[i] means the smallest index in s that can match t[i:m]
        # j = n - 1
        # for i in range(m - 1, -1, -1):
        #     while j >= 0 and s[j] != t[i]:
        #         j -= 1
        #     if j >= 0:
        #         right[i] = j
        #         j -= 1
    
        # # Step 3: Try all the ways to split t into two parts and calculate the score
        # # Case 1: No characters removed (if t is already a subsequence)
        # if left[-1] != -1:
        #     return 0
        
        # # Case 2: Remove some characters and keep left part from t[0:i] and right part from t[i:m]
        # res = float('inf')
        
        # # Only remove from the left or the right
        # for i in range(m):
        #     if right[i] != -1:
        #         res = min(res, i + 1)  # Remove t[0:i+1] (score is i+1)
        
        # for i in range(m - 1, -1, -1):
        #     if left[i] != -1:
        #         res = min(res, m - i)  # Remove t[i:m] (score is m-i)
        
        # # Try to remove the middle part
        # i, j = 0, m - 1
        # while i < m and j >= 0 and left[i] != -1 and right[j] != -1 and left[i] < right[j]:
        #     res = min(res, j - i - 1)
        #     i += 1
        #     j -= 1
        
        # return res if res != float('inf') else -1
        
        # # dp? max shared sequence, dp[i][j] = dp[i-1][j-1] + 1 if si == tj, dp[i-1][j], dp[i][j-1]
        # # This doesn't work, not nessarily he max shared sequnce is the soution 
        # m, n = len(s), len(t)
        # dp = [[0] * (n+1) for _ in range(m+1)]
        # dpl = [[[]] * (n+1) for _ in range(m+1)]
        # mx = 0
        # for i in range(m):
        #     for j in range(n):
        #         if s[i] == t[j]:
        #             dp[i+1][j+1] = dp[i][j] + 1
        #             mx = max(dp[i+1][j+1], mx)
        #             dpl[i+1][j+1] = dpl[i][j] + [j]
        #         else:
        #             if dp[i+1][j] >= dp[i][j+1]:
        #                 dp[i+1][j+1] = dp[i+1][j]
        #                 if len(dpl[i+1][j]) > 0:
        #                     dpl[i+1][j+1] = dpl[i+1][j]
        #             else:
        #                 dp[i+1][j+1] = dp[i][j+1]
        #                 if len(dpl[i][j+1]) > 0:
        #                     dpl[i+1][j+1] = dpl[i][j+1]
        # print(dp)
        # print(dpl)
        # res = n
        # for i in range(1, m+1):
        #     for j in range(1, n+1):
        #         if dp[i][j] != 0:
        #             st = set(dpl[i][j])
        #             l, r = 0, n-1
        #             while l < n and l in st:
        #                 l += 1
        #             if l == n:
        #                 return 0
        #             while r >= 0 and r in st:
        #                 r -= 1
        #             res = min(res, r - l + 1)
        # return res
22100