Substring Removal Hackerrank Solution
I dealt with this problem recently and it looks simple at first glance, but the mechanics of how removals chain together trip people up pretty often. The core idea is straightforward: you get a string s and a pattern t, and you repeatedly strip all non-overlapping occurrences of t from s. After each full pass, the remaining characters concatenate, which can create fresh occurrences that weren't there before. Your job is to count how many passes it takes, or report that it can't be done. Here's the actual thing that makes this problem tricky, and why a naive string replacement approach either times out or gets the answer wrong. When you remove one instance of the pattern, the gap closes. Characters that were separated by the removed substring now sit next to each other. They might form a brand new instance of the pattern. A standard replace-all in one language or another will only catch the ones present at the start of a pass, so you end up looping externally and rebuilding the string over and over. That's slow, and honestly, it's unnecessary.
How the stack-based approach actually works
The efficient solution mimics what the passes would do, but without the costly string reallocations. You iterate through s one character at a time, pushing each character onto a stack. After every push, if the stack is tall enough to hold the full pattern, you peek at the top m characters and compare them against t. When they match, you pop those m characters off and record one operation. The key detail most people miss is that you have to keep checking after the pop. Removing one occurrence might expose another match immediately, and since you're working on the stack, that next match is already there waiting. You loop on the check until it fails, then continue scanning the input. I spent too long on a version that only checked once per push because I was reading the problem statement too quickly and assumed one comparison per character was enough. The fix was literally wrapping the check in a while loop instead of an if statement. Here is what that looks like in code:
def removeOccurrences(s, t):
n = len(s)
m = len(t)
if m == 0 or n < m:
return -1
if t not in s:
return 0
stack = []
ops = 0
for char in s:
stack.append(char)
while len(stack) >= m:
if ''.join(stack[-m:]) == t:
for _ in range(m):
stack.pop()
ops += 1
else:
break
return ops if not stack else -1
That last condition is important and often overlooked. If the stack still has characters left at the end, it means the string was partially reduced but not completely eliminated. Depending on how the specific HackerRank variant phrases the return value, you might return the operation count anyway, or you might need to return -1 to indicate impossibility. Check the problem description carefully. One version returns the number of removals even if garbage remains. Another expects -1 when you can't clear the entire string. I lost a subtask once because I returned the count without checking the remainder. There is one edge case that took me a few debug cycles to handle properly. I was working with a string like "aabcbcbc" and a pattern of "abc". The first pass removes one "abc", leaving "aabc". The second pass removes another "abc", leaving "a". My first buggy version stopped after the first internal while loop iteration and missed the chained removal because the stack state after a pop wasn't being re-evaluated against the pattern correctly. The while loop approach fixes this, but you need to make sure your slice comparison is actually pulling from the end of the stack every time, not from a cached index. The time complexity is O(n * m) in the worst case because each character gets pushed once and the comparison slice takes O(m). For the typical HackerRank constraints, where n is usually under a few hundred thousand and m is small, this runs comfortably within the time limit. The space complexity is O(n) for the stack, which is fine.
Get the Full Details
If m is very large, close to n, the repeated slicing and string joining becomes the bottleneck. In that situation, you can avoid the ''.join() call by comparing character by character against the stack directly. It's a minor optimization but it saves noticeable time on the harder test cases where m is in the thousands and the pattern appears frequently. One thing that catches people out is assuming you can greedily remove the leftmost occurrence and move on. Greedy single-removal at a time works for counting total operations in some variants, but the stack method naturally handles all non-overlapping removals in the correct order. It processes left to right and removes as soon as a full pattern is visible, which is exactly what the problem definition requires. For those looking for a complete reference, the Substring Removal Hackerrank Solution follows this same stack pattern. There are a couple of variant problem IDs on HackerRank that adjust the return semantics slightly, so always verify whether the question asks for the number of removal operations or the final reduced string. I've seen both. The algorithm doesn't change, only the output formatting at the end.
Bottom line: use a stack, compare the tail after every insertion, loop on the comparison until it fails, and handle the empty-stack-or-not condition based on what the problem actually asks. The naive two-step approach of rebuild-then-search will work on easy samples but will time out on the medium and hard ones.
