Subsequence With the Minimum Score - Practice Coding Problems

Subsequence With the Minimum Score - Problem

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:

Let left be the minimum index among all removed characters.
Let right be the maximum index among all removed characters.

Then the score of the string is right - left + 1.

Return the minimum possible score to make t a subsequence of s.

A subsequence 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., "ace" is a subsequence of "abcde" while "aec" is not).

Input & Output

Example 1 — Basic Case

$ Input: s = "abacaba", t = "bzc"

› Output: 2

💡 Note: Remove "bz" from t, leaving "c". The character "c" exists in s as a subsequence. Score = 1 - 0 + 1 = 2.

Example 2 — Already Subsequence

$ Input: s = "abcdef", t = "ace"

› Output: 0

💡 Note: t is already a subsequence of s, so no characters need to be removed. Score = 0.

Example 3 — Remove Middle

$ Input: s = "xyz", t = "xay"

› Output: 1

💡 Note: Remove "a" from position 1, leaving "xy" which is a subsequence of "xyz". Score = 1 - 1 + 1 = 1.

Constraints

1 ≤ s.length, t.length ≤ 10⁵
s and t consist of only lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input

Two strings s and t

Find Removal

Identify minimum substring to remove from t

Check Subsequence

Verify remaining chars form subsequence of s

Key Takeaway

🎯 Key Insight: Match as much as possible from both ends of t with s, then remove the minimum middle section

Asked in

G Google 12 M Microsoft 8 A Amazon 6

The key insight is to find the minimum contiguous substring to remove from t such that the remaining characters form a subsequence of s. The optimal approach uses binary search on the answer combined with efficient subsequence checking. Time: O(n² log n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Substrings	O(n³)	O(1)	Try removing every possible substring from t and check if remainder is subsequence of s
Binary Search on Answer	O(n² log n)	O(1)	Binary search on the minimum possible score, checking if each score is achievable
Two Pointers - Match from Both Ends	O(n·m)	O(1)	Match as many characters as possible from left and right, remove the middle gap

Brute Force - Try All Substrings — Algorithm Steps

For each possible left index i
For each possible right index j >= i
Remove substring t[i:j+1] and check if remainder is subsequence of s

Visualization

Tap to expand

Step-by-Step Walkthrough

Input

s = "abacaba", t = "bzc"

Try Removals

Remove different substrings and check if remainder matches

Find Minimum

Return smallest score that works

Code -

solution.c — C

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int isSubsequence(char* text, char* pattern) {
    int i = 0, patLen = strlen(pattern), textLen = strlen(text);
    for (int j = 0; j < textLen && i < patLen; j++) {
        if (text[j] == pattern[i]) {
            i++;
        }
    }
    return i == patLen;
}

int solution(char* s, char* t) {
    int n = strlen(t);
    
    if (isSubsequence(s, t)) {
        return 0;
    }
    
    int minScore = n;
    char* remaining = (char*)malloc((n + 1) * sizeof(char));
    
    for (int left = 0; left < n; left++) {
        for (int right = left; right < n; right++) {
            strncpy(remaining, t, left);
            strcpy(remaining + left, t + right + 1);
            
            if (isSubsequence(s, remaining)) {
                int score = right - left + 1;
                if (score < minScore) {
                    minScore = score;
                }
            }
        }
    }
    
    free(remaining);
    return minScore;
}

int main() {
    char s[1001], t[1001];
    fgets(s, sizeof(s), stdin);
    fgets(t, sizeof(t), stdin);
    s[strcspn(s, "\n")] = 0;
    t[strcspn(t, "\n")] = 0;
    printf("%d\n", solution(s, t));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

O(n²) pairs of indices × O(n) subsequence check for each pair

⚠ Quadratic Growth

Space Complexity

O(1)

Only using variables for indices, no extra data structures

✓ Linear Space

8.5K Views

Medium Frequency

~35 min Avg. Time

234 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Substrings — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler