Skip to main content
Talentd

Find Maximum Removals From Source String - Solution & Explanation

MediumArrayHash TableTwo PointersString18 min readAsked at: Google
Practice this problem

Problem Statement

You are given a string source of size n, a string pattern that is a subsequence of source, and a sorted integer array targetIndices that contains distinct numbers in the range [0, n - 1].

We define an operation as removing a character at an index idx from source such that:

  • idx is an element of targetIndices.
  • pattern remains a subsequence of source after removing the character.

Performing an operation does not change the indices of the other characters in source. For example, if you remove 'c' from "acb", the character at index 2 would still be 'b'.

Return the maximum number of operations that can be performed.

 

Example 1:

Input: source = "abbaa", pattern = "aba", targetIndices = [0,1,2]

Output: 1

Explanation:

We can't remove source[0] but we can do either of these two operations:

  • Remove source[1], so that source becomes "a_baa".
  • Remove source[2], so that source becomes "ab_aa".

Example 2:

Input: source = "bcda", pattern = "d", targetIndices = [0,3]

Output: 2

Explanation:

We can remove source[0] and source[3] in two operations.

Example 3:

Input: source = "dda", pattern = "dda", targetIndices = [0,1,2]

Output: 0

Explanation:

We can't remove any character from source.

Example 4:

Input: source = "yeyeykyded", pattern = "yeyyd", targetIndices = [0,2,3,4]

Output: 2

Explanation:

We can remove source[2] and source[3] in two operations.

 

Constraints:

  • 1 <= n == source.length <= 3 * 103
  • 1 <= pattern.length <= n
  • 1 <= targetIndices.length <= n
  • targetIndices is sorted in ascending order.
  • The input is generated such that targetIndices contains distinct elements in the range [0, n - 1].
  • source and pattern consist only of lowercase English letters.
  • The input is generated such that pattern appears as a subsequence in source.

Approach Overview

Problem Overview: You are given a source string s, a pattern p, and a list of removable indices. Remove characters from s in the given order while keeping p a subsequence. The goal is to compute the maximum number of removals that still preserves the subsequence relationship.

Approach 1: Binary Search with Subsequence Validation (O(n log k) time, O(n) space)

The key observation: if removing k characters still keeps p as a subsequence, then removing fewer than k will also work. That monotonic property allows binary search on the number of removals. For a candidate value mid, mark the first mid indices as removed and scan the string using a two pointer subsequence check. One pointer walks through s, the other through p, skipping removed characters. If the pattern pointer reaches the end, the subsequence still exists. Adjust the binary search range accordingly. Each validation pass takes O(n), and binary search runs O(log k) times where k is the number of removable indices.

Approach 2: Two Pointer Greedy Simulation (O(n + k) time, O(n) space)

This approach simulates the removals directly while maintaining the subsequence check with two pointers. Use a boolean array to track removed positions in s. Iterate through the removal order and update the removed state. After each update, scan s using two pointers to verify whether p is still a subsequence. The pointer for s advances across the string while skipping removed indices, and the pointer for p advances only when characters match. The process stops when the subsequence condition breaks. The last valid removal count is the answer. The logic relies heavily on string traversal and pointer movement.

Recommended for interviews: Binary Search with Subsequence Validation is the approach most interviewers expect. It demonstrates recognition of a monotonic condition and combines binary search with a classic two‑pointer subsequence check. The greedy simulation helps build intuition, but the binary search solution shows stronger algorithmic thinking and handles larger inputs efficiently.

Approach 1: Binary Search with Subsequence Validation

This approach involves using binary search on the number of possible removals and validating whether the 'pattern' is still a subsequence after a certain number of removals. It leverages the fact that if 'pattern' is a subsequence after some removals, it will also be a subsequence with fewer removals.

This solution checks if 'pattern' remains a subsequence after a certain number of removals using a binary search strategy. A helper function is used to mark removable indices and checks if 'pattern' can still be formed from remaining characters.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n * log(m)) where n is the length of the source and m is the length of targetIndices.
Space Complexity: O(n), for maintaining the 'removed' boolean array.

Try this approach in the editor →

Approach 2: Two Pointer Greedy Approach

This technique uses a two-pointer approach to iteratively check and remove as long as 'pattern' remains a subsequence.

This approach attempts to remove as many characters as possible while pattern still forms a subsequence. It checks for every removal if it interrupts the formation of the pattern, and stops if it does, otherwise increases the count of valid removals.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n*m), iterating through the source and pattern for every potential removal.
Space Complexity: O(1), uses constant space.

Try this approach in the editor →

Approach 3: Dynamic Programming

We define f[i][j] to represent the maximum number of deletions in the first i characters of source that match the first j characters of pattern. Initially, f[0][0] = 0, and the rest f[i][j] = -infty.

For f[i][j], we have two choices:

  • We can skip the i-th character of source, in which case f[i][j] = f[i-1][j] + int(i-1 \in targetIndices);
  • If source[i-1] = pattern[j-1], we can match the i-th character of source, in which case f[i][j] = max(f[i][j], f[i-1][j-1]).

The final answer is f[m][n].

The time complexity is O(m times n), and the space complexity is O(m times n). Here, m and n are the lengths of source and pattern, respectively.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Binary Search with Subsequence Validation

Time Complexity: O(n * log(m)) where n is the length of the source and m is the length of targetIndices.
Space Complexity: O(n), for maintaining the 'removed' boolean array.

Two Pointer Greedy Approach

Time Complexity: O(n*m), iterating through the source and pattern for every potential removal.
Space Complexity: O(1), uses constant space.

Dynamic Programming—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Binary Search with Subsequence ValidationO(n log k)O(n)Best general solution when removable indices are large and you need an efficient check.
Two Pointer Greedy SimulationO(n + k) to O(nk) depending on validation frequencyO(n)Useful for understanding the subsequence validation process or when constraints are small.

Video Solution

Leetcode Biweekly Contest 141 | 3316. Find Maximum Removals From Source String | DP | Codefod • CodeFod • 1,602 views views

Watch 7 more video solutions →

Frequently Asked Questions

Is Find Maximum Removals From Source String easy or hard?
The problem is rated Medium because it requires recognizing a monotonic property and combining binary search with subsequence validation. The individual techniques are standard, but identifying that binary search on the answer works is the key insight.
Find Maximum Removals From Source String Python/Java solution
Most implementations follow the same structure: binary search the number of removable indices and validate with a two-pointer subsequence check. The logic is identical across Python, Java, C++, C#, and JavaScript with only syntax differences.
How to solve Find Maximum Removals From Source String in O(n log k)?
Use binary search on the number of characters removed. For each candidate value, mark the first k indices as removed and run a two-pointer subsequence check to see if the pattern still appears in the source string. If it does, increase k; otherwise decrease it. This efficiently finds the maximum valid removal count.
What is the best approach for Find Maximum Removals From Source String?
Binary search with subsequence validation is the most efficient and commonly expected solution. The idea is to binary search the number of removable characters and check whether the pattern remains a subsequence after removing those indices. Each validation uses a two-pointer subsequence scan of the string.
Is Find Maximum Removals From Source String asked at Google/Amazon/Meta?
Problems involving subsequence validation, binary search on answer, and greedy pointer scanning frequently appear in interviews at companies like Google, Amazon, and Meta. Variants of this problem test understanding of binary search over monotonic conditions and string subsequence checks.
What data structure is used in Find Maximum Removals From Source String?
The solution mainly uses arrays or boolean markers to track removed indices, along with two-pointer traversal of the strings. Binary search is applied on the answer space while the subsequence check operates directly on the string characters.
What is the time complexity of Find Maximum Removals From Source String?
The optimal solution runs in O(n log k) time where n is the length of the source string and k is the number of removable indices. Each binary search step performs a linear subsequence check using two pointers. Space complexity is O(n) for tracking removed positions.

Ready to solve this problem?

Practice Find Maximum Removals From Source String with our built-in code editor and test cases.

Practice on FleetCode
Previous

Delete Characters to Make Fancy String