Maximum Number of Removable Characters - Practice Coding Problems

Maximum Number of Removable Characters - Problem

You are given two strings s and p where p is a subsequence of s. You are also given a distinct 0-indexed integer array removable containing a subset of indices of s (s is also 0-indexed).

You want to choose an integer k (0 <= k <= removable.length) such that, after removing k characters from s using the first k indices in removable, p is still a subsequence of s. More formally, you will mark the character at s[removable[i]] for each 0 <= i < k, then remove all marked characters and check if p is still a subsequence.

Return the maximum k you can choose such that p is still a subsequence of s after the removals.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

Input & Output

Example 1 — Basic Case

$ Input: s = "abcacb", p = "ab", removable = [3,1,0]

› Output: 2

💡 Note: After removing indices 3 and 1: s becomes "a_c_cb" → "accb", which still contains "ab" as subsequence

Example 2 — Single Character

$ Input: s = "abcbddddd", p = "abcd", removable = [3,2,1,4,7,6]

› Output: 4

💡 Note: Remove indices [3,2,1,4] to get "a___d_ddd" → "adddd", still contains "abcd" subsequence

Example 3 — No Removals Possible

$ Input: s = "abcab", p = "abc", removable = [0,1,2]

› Output: 0

💡 Note: Removing any character breaks the subsequence, so maximum k = 0

Constraints

1 ≤ p.length ≤ s.length ≤ 10⁵
0 ≤ removable.length < s.length
0 ≤ removable[i] < s.length
p is a subsequence of s
s and p consist of lowercase English letters
The elements in removable are distinct

Visualization

Tap to expand

Understanding the Visualization

Input

String s, target subsequence p, and removable indices

Binary Search

Find maximum k where p remains subsequence after removing k characters

Output

Return the maximum valid k

Key Takeaway

🎯 Key Insight: Use binary search on the answer since the problem has monotonic property - if k works, all smaller values work too

Asked in

G Google 15 f Facebook 12 a Amazon 8

The key insight is recognizing this is a binary search on answer problem. Since if we can remove k characters and maintain the subsequence, we can also remove any number < k (monotonic property). The optimal approach uses binary search to find the maximum k, checking subsequence validity for each candidate. Time: O(log r × (n + m)), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Binary Search on Answer	O(log r × (n + m))	O(n)	Use binary search to find maximum k efficiently
Linear Search	O(n × m × r)	O(n)	Try each possible k from 0 to removable.length linearly

Binary Search on Answer — Algorithm Steps

Step 1: Set left=0, right=removable.length
Step 2: For mid=(left+right)/2, check if k=mid works
Step 3: If valid, try larger k (left=mid+1), else try smaller (right=mid-1)
Step 4: Return the maximum valid k found

Visualization

Tap to expand

Step-by-Step Walkthrough

Set Range

left=0, right=removable.length

Test Middle

Check if mid value works, adjust search range

Converge

Find maximum valid k in O(log n) steps

Code -

solution.c — C

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

bool isSubsequence(char* s, char* p, bool* removed, int sLen, int pLen) {
    int i = 0;
    for (int j = 0; j < sLen; j++) {
        if (removed[j]) continue;
        if (i < pLen && s[j] == p[i]) {
            i++;
        }
    }
    return i == pLen;
}

bool canRemoveK(char* s, char* p, int* removable, int k, int sLen, int pLen) {
    bool* removed = calloc(sLen, sizeof(bool));
    for (int i = 0; i < k; i++) {
        removed[removable[i]] = true;
    }
    bool result = isSubsequence(s, p, removed, sLen, pLen);
    free(removed);
    return result;
}

int solution(char* s, char* p, int* removable, int removableSize) {
    int sLen = strlen(s);
    int pLen = strlen(p);
    int left = 0, right = removableSize;
    int result = 0;
    
    while (left <= right) {
        int mid = (left + right) / 2;
        if (canRemoveK(s, p, removable, mid, sLen, pLen)) {
            result = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return result;
}

int main() {
    char s[100001], p[100001], line[500001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    fgets(p, sizeof(p), stdin);
    p[strcspn(p, "\n")] = 0;
    
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    // Parse array
    int removable[100000];
    int removableSize = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        removable[removableSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    printf("%d\n", solution(s, p, removable, removableSize));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(log r × (n + m))

Binary search O(log r) times, each check takes O(n+m) for subsequence verification

⚡ Linearithmic

Space Complexity

O(n)

Set to track removed indices during each check

⚡ Linearithmic Space

28.4K Views

Medium Frequency

~25 min Avg. Time

856 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

Binary Search on Answer — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler