Remove All Occurrences of a Substring LeetCode Solution

Problem Statement

The Remove All Occurrences of a Substring LeetCode Solution –“Remove All Occurrences of a Substring” states that remove ALL the occurrences of the substring part from the given input string s.

Note: Substring is a contiguous sequence of characters in an input string.

Example

 Explanation

Let’s look at how the series of steps performed on an input string daabcbaabcbc,

1.  First occurrence of part string ‘abc’ found at index 2 so remove it. After that, the resultant string becomes dabaabcbc.

2. Found the next occurrence of part string ‘abc’ at index 4 so remove it. After that, the resultant string becomes dababc.

3. Found the next occurrence of part string ‘abc’ at index 3 so remove that part. After that, the resultant string becomes dab.

4.  Now, there are no occurrences of part string present in the final string so return the resultant string as an output.

 Idea

Use the indexOf() and substring() operation presents in the Java String Utility Class.

 Code

  Java Program of Remove All Occurrences of a Substring

   class Solution {

               public String removeOccurrences(String s, String part) {

                         if(part.length() == 0||part.length() > s.length()) 
                              return s; 
                         int occIndex = s.indexOf(part); 
                         while(occIndex!=-1) { 
                               s = s.substring(0, occIndex).concat(s.substring(occIndex + part.length())); 
                               occIndex = s.indexOf(part); 
                         } 
                         return s;
                }
   }

  C++ Program of Remove All Occurrences of a Substring

 class Solution {
   public:
          string removeOccurrences(string s, string part) {
               int i=0; 
               int len = s.length(); 
               string finalRes = s; 
               while(i < len) { 
                   string s= finalRes; 
                   if(s.find(part) < s.length()) 
                   { 
                         int occInd = s.find(part); 
                         finalRes.erase(occInd, part.length()); 
                   } 
                   i++; 
               } 
               return finalRes;
          }
};

  Complexity Analysis for Remove All Occurrences of a Substring LeetCode Solution

     Time Complexity

Assume L – Length of an input string

The indexOf() and substring() operation finds the index and parts the string in a linear time respectively. As a result,  the overall time complexity of the solution is O(L).

     Space Complexity

The substring() operation creates a new copy of the string every time it removes the occurrences. As a result, the overall space complexity of the solution is O(L).

Reference: https://www.javaguides.net/2018/08/java-string-utility-class.html