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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Subsequence With the Minimum Score

Difficulty: Hard

Problem 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, it is calculated based on the minimum and maximum indices of the removed characters. Return the minimum possible score to make t a subsequence of s.

Key Insights

  • A subsequence allows characters to be removed without changing the order of the remaining characters.
  • The score is based on the indices of removed characters, specifically the range from left to right.
  • The goal is to minimize the score while ensuring t becomes a subsequence of s.
  • Two-pointer technique can be helpful in comparing the two strings efficiently.

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(1), as we only use a few extra variables for indices.

Solution

To solve the problem, we can use a two-pointer approach. We will use two pointers to track our position in both strings, s and t. Our aim is to find the longest prefix of t that can be matched with s from the left and the longest suffix of t that can be matched with s from the right. The minimum score will be the number of characters in t that are not part of this matching.

  1. Start with two pointers, one at the beginning of t and another at the end.
  2. Move the left pointer of t rightward to find the longest matching prefix in s.
  3. Move the right pointer of t leftward to find the longest matching suffix in s.
  4. Calculate the score as the number of characters in t that are not matched.

This approach ensures we efficiently calculate the minimum score needed to make t a subsequence of s.

Code Solutions

def minimum_score(s: str, t: str) -> int:
    n, m = len(s), len(t)
    
    # Find the longest prefix of t in s
    left = 0
    while left < m and (left < n and s[left] == t[left]):
        left += 1
    
    # Find the longest suffix of t in s
    right = m - 1
    while right >= 0 and (n - 1 - (m - 1 - right) >= 0 and s[n - 1 - (m - 1 - right)] == t[right]):
        right -= 1
    
    # Calculate the score
    return max(0, right - left + 1)
← Back to All Questions