Leetcode Problem 2565. Subsequence With the Minimum Score

2565. Subsequence With the Minimum Score

Leetcode Solutions

Greedy Prefix and Suffix Matching with Binary Search

  1. Create two lists, leftSs and rightSs, to store the indices of s that match the prefix and suffix of t respectively.
  2. Iterate over s and t from the beginning to find the prefix match and store the indices in leftSs.
  3. Iterate over s and t from the end to find the suffix match and store the indices in rightSs.
  4. Initialize the result with the minimum of the unmatched parts of t from both ends.
  5. Iterate over rightSs and for each index, use binary search on leftSs to find the maximum non-overlapping prefix of t.
  6. Update the result with the minimum score found.
  7. Return the result as the minimum score.
UML Thumbnail

Prefix-Suffix Array with Greedy Matching

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...