Abstract / Summary

Find the longest part of the string where each letter appears at most as many times as it does in the whole string.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 48% (90k+ submissions).

Typical patterns to solve this problem:

• Array
• Binary Search
• String
• Two Pointers

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation solves the “maximum removals” problem: given a source string s, a target pattern p, and an ordered list removable of indices that may be deleted from s, it returns the largest number of deletions that still allow p to appear as a subsequence of the modified s. The solution uses a binary search over the possible count of deletions and a helper routine that checks feasibility for a given prefix of removable.

Core Logic

Feasibility Check

The inner function impossible(k) determines whether removing the first k indices from removable makes it impossible to embed p as a subsequence of s. It first extracts the relevant removal positions, sorts them, and then walks through s while simultaneously tracking the progress through p.

def impossible(k):
    # relevant indices
    remove = sorted(removable[:k])

    b = 0  # index for p
    r = 0  # index for remove
    for a in range(len(s)):
        if r < len(remove) and remove[r] == a:
            # skip
            r += 1
        else:
            # try to extend subsequence
            if s[a] == p[b]:
                b += 1
                if b == len(p):
                    # full subsequence found, it's possible => not impossible
                    return False
    return True  # failed to build subsequence

The loop iterates over each character position a in s. When the current position matches the next removal index, the character is ignored and the removal pointer r advances. Otherwise, the character is compared with the current target character p[b]. A match advances the pattern pointer b. If the entire pattern is matched (b == len(p)), the function returns False, indicating that the removals do not make the task impossible. If the loop finishes without completing the pattern, it returns True.

Binary Search

The outer call uses bisect_left to locate the smallest k for which impossible(k) becomes true. Subtracting one yields the greatest k that still permits the subsequence.

return bisect_left(range(len(removable) + 1), True, key=impossible) - 1

bisect_left treats the range [0, len(removable)] as a monotonic sequence where the predicate impossible(k) transitions from False to True. The binary search therefore runs in logarithmic steps relative to the length of removable.

Edge Cases Handled

When k is zero, remove becomes an empty list; the loop then processes the original string without skipping any characters, correctly handling the case where no deletions are performed.

If k equals the length of removable, all specified indices are removed. The sorted remove list contains every index that may be skipped, and the algorithm still correctly attempts to match p against the remaining characters.

The code also gracefully handles the situation where p is longer than the remaining characters after removals; the inner loop will exhaust s without reaching b == len(p), causing impossible to return True.

When p is an empty string, the condition b == len(p) is satisfied immediately (since len(p) is zero). The function will return False on the first iteration, indicating that an empty pattern is always a subsequence, regardless of removals.

If removable contains duplicate indices, sorting and iterating over them still works because each duplicate will be encountered in order; the skip logic will simply ignore the same position multiple times, which does not affect correctness because a character can be removed only once.

Performance Optimizations

The algorithm avoids reconstructing the modified string for each feasibility check. Instead of building a new string after deletions, it uses two pointers (r for removals and b for the pattern) to simulate the effect of removals on the fly. This in-place simulation eliminates the overhead of string slicing or list construction, keeping the inner loop tight and memory-light.

Sorting the slice removable[:k] inside impossible could be costly if performed repeatedly. However, because k grows monotonically during the binary search, the sorted order of the prefix is the same as the original order of removable if removable is already sorted. In typical problem statements, removable is provided in increasing order, so the sorted call becomes a no-op, effectively a linear pass.

The use of Python’s built-in bisect_left leverages a highly optimized binary search implementation written in C, reducing the overhead of the search loop compared to a manual Python implementation.

Overall, the combination of on-the-fly character skipping, pointer-based subsequence matching, and a C-level binary search yields a solution that scales efficiently with the size of the input strings and the removal list.

Imagine a long mystery word made of colorful blocks. Some of the blocks are marked to be taken away. This code acts like a helper who wants to see how many blocks can be removed while still keeping a hidden treasure word hidden inside the main word.

To figure this out, the code picks a number of blocks to pull out of the line. It then looks at the remaining blocks to see if the treasure word is still there. It does this by checking each letter in the main word one by one. If a block is marked to be kicked out, the helper skips over it. If the block stays, the helper checks if it matches the next letter of the treasure word.

If the whole treasure word is found, the helper knows that removing that many blocks is safe. If the treasure word disappears, the helper knows too many blocks were pulled out. By guessing different amounts, the code eventually finds the highest number of blocks that can be removed without losing the treasure.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

not analyzed yet

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++		Python	Java				TS
	WalkCCC	C++		Python	Java
	leetcode.ca	C++	JS	Python	Java		Go	Rust	TS
	Progiez	C++		Python	Java
github	black-shadows	C++
	charles-wangkai				Java
	everthis		JS
	fsq	C++
	JoshCrozier		JS
	lkwq007			Python
	suxrobGM					C#
	wisdompeak	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, JavaScript, Python, Rust, TypeScript
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fsq	C++
JoshCrozier	JavaScript
lkwq007	Python
suxrobGM	C#
wisdompeak	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality