Package g2501_2600.s2565_subsequence_with_the_minimum_score

Class Solution

java.lang.Object
g2501_2600.s2565_subsequence_with_the_minimum_score.Solution
public class Solution extends Object
2565 - Subsequence With the Minimum Score.<p>Hard</p> <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>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>&ldquo;<ins>a</ins>b<ins>c</ins>d<ins>e</ins>&rdquo;</code> while <code>&quot;aec&quot;</code> is not).</p> <p><strong>Example 1:</strong></p> <p><strong>Input:</strong> s = &ldquo;abacaba&rdquo;, t = &ldquo;bzaa&rdquo;</p> <p><strong>Output:</strong> 1</p> <p><strong>Explanation:</strong> In this example, we remove the character &ldquo;z&rdquo; at index 1 (0-indexed). The string t becomes &ldquo;baa&rdquo; which is a subsequence of the string &ldquo;abacaba&rdquo; and the score is 1 - 1 + 1 = 1. It can be proven that 1 is the minimum score that we can achieve.</p> <p><strong>Example 2:</strong></p> <p><strong>Input:</strong> s = &ldquo;cde&rdquo;, t = &ldquo;xyz&rdquo;</p> <p><strong>Output:</strong> 3</p> <p><strong>Explanation:</strong> In this example, we remove characters &ldquo;x&rdquo;, &ldquo;y&rdquo; and &ldquo;z&rdquo; at indices 0, 1, and 2 (0-indexed). The string t becomes &quot;&quot; which is a subsequence of the string &ldquo;cde&rdquo; and the score is 2 - 0 + 1 = 3. It can be proven that 3 is the minimum score that we can achieve.</p> <p><strong>Constraints:</strong></p> <ul> <li><code>1 <= s.length, t.length <= 10<sup>5</sup></code></li> <li><code>s</code> and <code>t</code> consist of only lowercase English letters.</li> </ul>

  • Constructor Details

    • Solution

      public Solution()

  • Method Details

    • minimumScore

      public int minimumScore(String s, String t)