Leetcode 1910: Remove All Occurrences of a Substring
Given two strings s and part, perform the following operation on s until all occurrences of the substring part are removed. Find the leftmost occurrence of the substring part and remove it from s. Return s after removing all occurrences of part.
Problem
Approach
Steps
Complexity
Input: The input consists of two strings: s and part. s is the main string, and part is the substring to be removed.
Example: s = "abcdefghabcxyz", part = "abc"
Constraints:
• 1 <= s.length <= 1000
• 1 <= part.length <= 1000
• s and part consist of lowercase English letters.
Output: Return the string s after all occurrences of part have been removed.
Example: "defghxyz"
Constraints:
Goal: To remove all occurrences of part from s, starting with the leftmost and continuing until no more occurrences remain.
Steps:
• Iterate over the string s and remove the leftmost occurrence of part.
• After each removal, continue searching for the next occurrence of part.
• Repeat until no more occurrences of part exist in the string.
Goal: Ensure the solution handles the constraints efficiently, considering the input size.
Steps:
• The length of the string s is between 1 and 1000.
• The length of the substring part is between 1 and 1000.
• Both s and part contain only lowercase English letters.
Assumptions:
• The part substring will be checked for removal until no more occurrences exist.
• Input: s = "abcdefghabcxyz", part = "abc"
• Explanation: By removing 'abc' starting from index 0, then index 4, we are left with the string 'defghxyz'.
Approach: The approach involves repeatedly finding and removing the leftmost occurrence of part in s until no more instances of part are present.
Observations:
• We need an efficient method to perform substring search and removal.
• Using string search and manual removal will be the main technique.
Steps:
• Iterate through the string and look for the substring part.
• Once found, remove it from the string.
• Continue this process until part is no longer found in the string.
Empty Inputs:
• If the string s or part is empty, handle gracefully.
Large Inputs:
• Ensure the solution works efficiently for the maximum string length of 1000.
Special Values:
• Handle cases where s and part are the same.
Constraints:
• s and part must be non-empty and contain lowercase English letters.
string removeOccurrences(string s, string part) {
string x = s;
int m = part.size(), n = s.size(), i, j;
for(i = 0, j = 0; i < n; i++) {
x[j++] = s[i];
if (j >= m && x.substr(j - m, m) == part)
j -= m;
}
return x.substr(0, j);
}
1 : Function Definition
string removeOccurrences(string s, string part) {
Define a function 'removeOccurrences' which takes two strings 's' and 'part' as input.
2 : Variable Initialization
string x = s;
Initialize a new string 'x' with the value of string 's' to modify the string without affecting the original.
3 : Variable Declaration
int m = part.size(), n = s.size(), i, j;
Declare and initialize the variables: 'm' for the length of 'part', 'n' for the length of 's', and 'i' and 'j' for loop indices.
4 : Loop Setup
for(i = 0, j = 0; i < n; i++) {
Start a loop that iterates over each character of string 's'.
5 : Character Assignment
x[j++] = s[i];
Copy each character from 's' to 'x', increasing the index 'j' as we progress through the string.
6 : Substring Check
if (j >= m && x.substr(j - m, m) == part)
Check if the last 'm' characters of 'x' match the substring 'part'. If so, adjust the index 'j' to remove the matched part.
7 : Rollback Indices
j -= m;
If the substring 'part' is found, roll back the index 'j' by 'm' to remove the last occurrence.
8 : Return Statement
return x.substr(0, j);
Return the modified string 'x' up to the last valid character position 'j'.
Best Case: O(n), where n is the length of string s.
Average Case: O(n * m), where n is the length of s and m is the length of part.
Worst Case: O(n * m), where n is the length of s and m is the length of part.
Description: The best case occurs when no occurrences of part are found in s.
Best Case: O(1), if no new string is created during processing.
Worst Case: O(n), where n is the length of string s.
Description: We store the result string after performing all removals.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus