Subsequence With the Minimum Score

The brute-force approach systematically explores every possible scenario. We can remove any contiguous subsegment of characters from t. The idea is to try removing every possible substring t[i...j], check if the remaining parts of t form a subsequence of s, and if they do, we consider the length of the removed substring as a potential answer. We keep track of the minimum length found so far.

1. Initialize min_score to the length of t, m. This is the score if we remove the entire string t.
2. Check if t is already a subsequence of s. If so, the score is 0, and we can return immediately.
3. Iterate through all possible contiguous substrings t[i...j] to remove. This can be done with two nested loops:
   • The outer loop for the start index i from 0 to m.
   • The inner loop for the end index j from i to m.
4. For each pair (i, j), we are considering removing the substring t[i...j-1]. The length of this removal is j - i.
5. Construct the remaining string t_rem by concatenating the prefix t[0...i-1] and the suffix t[j...m-1].
6. Check if t_rem is a subsequence of s using a helper function. This check can be done in O(s.length() + t_rem.length()) time with a two-pointer approach.
7. If t_rem is a subsequence of s, update min_score = min(min_score, j - i).
8. After checking all (i, j) pairs, min_score will hold the minimum possible score.

This method iterates through all O(m^2) possible contiguous subsegments of t to remove. For each subsegment, defined by start and end indices i and j, we form a new string by taking t's prefix up to i and suffix from j. Then, we perform a subsequence check to see if this new string is a subsequence of s. The subsequence check itself takes time proportional to the lengths of the strings involved. The minimum length of a valid removal (j - i) is recorded. This process guarantees finding the minimum score but is computationally very expensive.

class Solution {
    public int minimumScore(String s, String t) {
        int m = t.length();
        int n = s.length();
        int minScore = m;

        // Case: remove nothing
        if (isSubsequence(s, t)) {
            return 0;
        }

        // Iterate through all substrings t[i...j-1] to remove
        for (int i = 0; i <= m; i++) {
            for (int j = i; j <= m; j++) {
                // Removed part is t[i...j-1]
                String prefix = t.substring(0, i);
                String suffix = t.substring(j);
                String remainingT = prefix + suffix;

                if (isSubsequence(s, remainingT)) {
                    minScore = Math.min(minScore, j - i);
                }
            }
        }
        return minScore;
    }

    private boolean isSubsequence(String s, String t) {
        int i = 0, j = 0;
        while (i < s.length() && j < t.length()) {
            if (s.charAt(i) == t.charAt(j)) {
                j++;
            }
            i++;
        }
        return j == t.length();
    }
}