1910. Remove All Occurrences of a Substring
Problem Description
The task described in the LeetCode problem is about string manipulation. You are given two strings s
and part
. Your goal is to repeatedly find the leftmost occurrence of the string part
in s
and remove it. You should keep doing this operation until part
can no longer be found within s
. To clarify, a substring is a sequence of characters that appear in consecutive order within another string. The operation is only complete when there are no more sequences of characters in s
that match part
. The output should be the resulting string s
after all possible removals of the substring part
have been conducted.
Intuition
To solve the problem, one can use the built-in string methods available in python. The intuition lies in searching for the substring part
within the string s
and removing the leftmost occurrence of it. This can be done iteratively using a while
loop, which continues as long as part
is found in s
.
To implement this:
- Check if
part
is a substring ofs
using thein
keyword. - If it is, use the
replace
method of the string object, which replaces the first occurrence ofpart
ins
with an empty string (effectively removing it), but make sure to limit the replacement to just one occurrence by passing1
as the second argument toreplace
. - Return the modified string
s
once there are no more occurrences ofpart
in it.
The key here is that the replace
function is used in a controlled manner to only remove the first (leftmost) occurrence of part
within each iteration, ensuring that the algorithm works as intended by the problem description.
Solution Approach
The implementation of the solution is straightforward and relies primarily on Python's string processing capabilities. Here's a step-by-step explanation of the approach using algorithms and data structures:
- Algorithm: Iterative Removal
- The algorithm uses a loop to repeatedly search and remove the substring
part
froms
. It continues to do so until thepart
can no longer be found withins
.
- The algorithm uses a loop to repeatedly search and remove the substring
- Data Structure: String
- Strings are the primary data structure used in this problem. In Python, strings are immutable, meaning a new string is created each time you modify it.
Given the Python code snippet:
1class Solution:
2 def removeOccurrences(self, s: str, part: str) -> str:
3 while part in s:
4 s = s.replace(part, '', 1)
5 return s
Here's an explanation of the code:
- While Loop:
- The
while
loop checks whetherpart
is still a substring ofs
. The conditionpart in s
returns a boolean value -True
ifpart
is found ins
andFalse
otherwise.
- The
- String Replacement:
- Inside the loop, the
replace
method is called ons
. The first argument is the substringpart
we are looking for, the second argument is an empty string to which the foundpart
will be replaced, signifying its removal. The third argument1
ensures that only the first instance ofpart
is replaced, which corresponds to the "leftmost occurrence".
- Inside the loop, the
- Return value:
- Once the loop terminates (when
part
is not found ins
), the final version ofs
is returned, which no longer contains any occurrences ofpart
.
- Once the loop terminates (when
No complex patterns or sophisticated algorithms are needed beyond the basic iterative approach. The solution leverages Python's built-in string methods to achieve the result with a clean and easy-to-understand implementation.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
To illustrate the solution approach, let's go through a small example. Imagine we have the string s = "axbxcx"
and the substring part = "x"
. Our goal is to remove the leftmost occurrence of x
from s
until x
can no longer be found in s
.
Here's how the implementation works step by step:
- Initial:
s = "axbxcx"
,part = "x"
- First Iteration:
- Check if
part
is ins
:x
is in"axbxcx"
- Replace the first occurrence of
part
with an empty string:- Before:
s = "axbxcx"
- After:
s = "abxcx"
(we removed the firstx
)
- Before:
- Check if
- Second Iteration:
- Check if
part
is ins
again:x
is in"abxcx"
- Replace the first occurrence of
part
with an empty string:- Before:
s = "abxcx"
- After:
s = "abcx"
(we removed the secondx
)
- Before:
- Check if
- Third Iteration:
- Check if
part
is ins
again:x
is in"abcx"
- Replace the first occurrence of
part
with an empty string:- Before:
s = "abcx"
- After:
s = "abc"
(we removed the lastx
)
- Before:
- Check if
- Final Check:
part
is no longer ins
:x
is not in"abc"
The resulting string s
is "abc"
because all instances of part
have been removed. This gives us the output of the function. Using the provided code snippet, the final return statement return s
would give us "abc"
as the solution to our input example.
Solution Implementation
1class Solution:
2 def remove_occurrences(self, string: str, part: str) -> str:
3 # Repeatedly search for the 'part' in 'string' and remove its first occurrence
4 while part in string:
5 # Find the index of the first occurrence of 'part'
6 index = string.find(part)
7 # Remove 'part' by slicing the string before and after 'part'
8 string = string[:index] + string[index+len(part):]
9
10 # Return the modified string after removing all occurrences of 'part'
11 return string
12
13# Example usage:
14# sol = Solution()
15# new_string = sol.remove_occurrences("daabcbaabcbc", "abc")
16# print(new_string) # Output would be "dab"
17
1class Solution {
2
3 /**
4 * Removes all occurrences of the substring 'part' from the string 's'.
5 *
6 * @param s The original string from which occurrences of 'part' will be removed.
7 * @param part The substring to be removed from 's'.
8 * @return The modified string with all occurrences of 'part' removed.
9 */
10 public String removeOccurrences(String s, String part) {
11 // Keep removing 'part' from 's' while 's' contains 'part'
12 while (s.contains(part)) {
13 // Replace the first occurrence of 'part' in 's' with an empty string
14 s = s.replaceFirst(part, "");
15 }
16 return s;
17 }
18}
19
1class Solution {
2public:
3 // Function to remove all occurrences of a substring 'part' from the string 's'
4 string removeOccurrences(string s, string part) {
5 // Get the size of the substring 'part'
6 int partSize = part.size();
7
8 // Find the first occurrence of 'part' in 's'
9 size_t position = s.find(part);
10
11 // Continue looping as long as 'part' is found in 's'
12 while (position != string::npos) {
13 // Erase 'part' from 's'
14 s.erase(position, partSize);
15 // Find the next occurrence of 'part' in 's'
16 position = s.find(part);
17 }
18 // Return the modified string with all 'part' occurrences removed
19 return s;
20 }
21};
22
1/**
2 * Removes all occurrences of a specified substring from the given string.
3 * @param {string} str - The original string from which to remove occurrences.
4 * @param {string} part - The substring to remove from the original string.
5 * @returns {string} The modified string with all occurrences of the substring removed.
6 */
7function removeOccurrences(str: string, part: string): string {
8 // Continue to look for the substring `part` in `str` until it cannot be found
9 while (str.includes(part)) {
10 // Replace the first occurrence of `part` in `str` with an empty string
11 str = str.replace(part, '');
12 }
13 // Return the modified string with all occurrences of `part` removed
14 return str;
15}
16
Time and Space Complexity
Time Complexity
The provided function's time complexity can be analyzed based on the while
loop and the str.replace()
method used within it.
- The
while
loop runs as long as the substringpart
is found within the strings
. str.replace()
is called each time thepart
is found, and it has a complexity ofO(n)
in the worst case, wheren
is the length of strings
, since in the worst case it has to scan the entire string to replace the occurrences.
If m
is the length of the substring part
, the worst-case scenario occurs when part
is found in s
multiple times and the positions of part
in s
are distributed such that most of the string has to be scanned for each replacement. Therefore, the complexity can approximately be O((n - m + 1) * n)
because it could take up to (n - m + 1)
searches through the string s
.
Hence, the worst-case time complexity is O((n - m + 1) * n)
.
Space Complexity
The space complexity of the function arises from the storage required for the input string s
and the additional strings created during the replacements.
- The input string
s
has a space complexity ofO(n)
, wheren
is its length. - Each time a replacement is performed, a new string is created, and this new string could have a length up to
n - m
.
Given that only one replacement string exists at a time (the previous is discarded when the new one is created), the additional space required for the algorithm as a result of replacements is also O(n)
.
Therefore, the overall space complexity of the algorithm is O(n)
.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of these properties could exist for a graph but not a tree?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.