We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Subsequence With the Minimum Score

Number: 2701

Difficulty: Hard

Paid? No

Companies: Meesho, DoorDash

Problem Description

Given two strings s and t, you are allowed to remove any number of characters from t. The score is defined as 0 when no characters are removed; otherwise, if the removed characters’ minimum index is left and the maximum index is right, then the score is (right - left + 1). Your goal is to remove a contiguous block (by definition of score) from t such that the remaining characters (which keep their original order) form a subsequence of s, and you want to minimize the score (i.e. the length of the removed block).

Key Insights

  • Removing characters non-contiguously has the same score as removing the contiguous block covering their min and max indices.
  • The problem becomes: find a contiguous block from t whose removal makes the remaining string (prefix and suffix) a subsequence of s.
  • Precompute for every prefix of t the earliest positions in s where they appear as a subsequence (left array).
  • Similarly, precompute for every suffix of t the latest positions in s (right array).
  • Use a two-pointer (or binary search) technique to try all possible splits between the kept prefix and suffix from t and minimize the removed block length.

Space and Time Complexity

Time Complexity: O(n + m), where n is the length of s and m is the length of t. Space Complexity: O(m) for storing the left and right arrays.

Solution

We first determine if t is already a subsequence of s by computing for each character in t its first matching position in s (left array) by iterating forward. Similarly, we go backwards through t and s to build a right array that stores the latest matching positions for each character from the end of t.

Once we have the left and right arrays:

  • The left array at index i indicates the earliest index in s where t[0...i] can be matched.
  • The right array at index i indicates the latest index in s where t[i...end] can be matched.

For every possible split of t into two parts (prefix t[0...i-1] and suffix t[j...end]), we want to ensure that the last index matched from the prefix in s (from left[i-1]) is strictly less than the first index matched from the suffix in s (from right[j]). This guarantees that when we remove the block t[i...j-1], the concatenation is a valid subsequence of s.

By scanning over i and j with a two-pointer approach, we compute the minimal removal length (j - i). If t is already a subsequence (i.e. removal length = 0 is possible), we return 0 as the answer.

Code Solutions

# Python solution

def minimumScore(s: str, t: str) -> int:
    n, m = len(s), len(t)
    
    # left[i]: the earliest index in s where t[0...i] is matched
    left = [0] * m
    j = 0
    for i in range(m):
        # Move in s until we find t[i]
        while s[j] != t[i]:
            j += 1
        left[i] = j
        j += 1  # move to next index in s
    
    # right[i]: the latest index in s where t[i...end] is matched
    right = [0] * m
    j = n - 1
    for i in range(m - 1, -1, -1):
        # Move backward in s until we find t[i]
        while s[j] != t[i]:
            j -= 1
        right[i] = j
        j -= 1  # move to previous index in s
    
    # Initialize answer as the case when entire t is removed
    ans = m  
    # Option 1: Remove prefix: check removal from index 0 to j-1 (keep suffix only)
    ans = min(ans, right[0])
    # Option 2: Remove suffix: check removal from index i to m-1 (keep prefix only)
    ans = min(ans, m - 1 - left[m - 1])
    
    # Two pointers over possible splits: prefix [0...i-1] and suffix [j...m-1]
    j_ptr = 0
    for i in range(m):
        # Move j_ptr to maintain condition: left[i] < right[j_ptr]
        while j_ptr < m and left[i] >= right[j_ptr]:
            j_ptr += 1
        if j_ptr < m:
            # Removed block is from i+1 to j_ptr-1. Its length is j_ptr - i - 1 + 1 = j_ptr - i.
            ans = min(ans, j_ptr - i - 1)
    return ans

# Example usage:
s = "abacaba"
t = "bzaa"
print(minimumScore(s, t))  # Expected output: 1
← Back to All Questions