Minimize length of a string by removing occurrences of another string from it as a substring

0 0 6 minutes read

Given a string S and a string T, the task is to find the minimum possible length to which the string S can be reduced to after removing all possible occurrences of string T as a substring in string S.

Examples:

Input: S = “aabcbcbd”, T = “abc”
Output: 2
Explanation:
Removing the substring {S[1], …, S[3]} and modifies the remaining string to “abcbd”.
Removing the substring {S[0] .. S[2]}, the resultant string modifies to “bd”.
Therefore, the required answer is 2.

Input: S = “asdfbc”, T = “xyz”
Output: 0
Explanation:
No occurrence of the string “xyz” as a substring in S.

Approach: The idea is to iterate over the characters of the given string and initialize an auxiliary string and check if the newly formed string is present as a substring in the given string. If found to be true, then simply remove that substring from the given string.

Follow the steps below to solve this problem:

First, identify the substrings T by traversing through the string and keeping track of the characters encountered.
But, when the substring is removed, the concatenation of the remaining parts is expensive as each character has to move backwards by M places.
In order to avoid this, maintain a string, say temp, which contains only the characters iterated so far.
Hence, if the required substring is present in temp, then just remove the last M characters in constant computational time.
Finally, print the minimized length of the string after performing all operations.

Below is the implementation of the above approach:

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to minimize length of
// string S after removing all
// occurrences of string T as substring
void minLength(string& S, string& T,
               int N, int M)
{
    string temp;
 
    // Count of characters
    // required to be removed
    int subtract = 0;
 
    // Iterate over the string
    for (int i = 0; i < N; ++i) {
 
        // Insert the current
        // character to temp
        temp.push_back(S[i]);
 
        // Check if the last M
        // characters forms t or not
        if (temp.size() >= M) {
 
            // Getting the last M
            // characters. If they
            // are equal to t then
            // remove the last M
            // characters from the temp string
            if (temp.substr(temp.size() - M, M) == T) {
 
                // Incrementing subtract by M
                subtract += M;
 
                // Removing last M
                // characters from the
                // string
                int cnt = 0;
                while (cnt != M) {
                    temp.pop_back();
                    ++cnt;
                }
            }
        }
    }
 
    // Print the final answer
    cout << (N - subtract) << "\n";
}
 
// Driver Code
int main()
{
    // Given string S & T
    string S = "aabcbcbd", T = "abc";
 
    // Length of string S
    int N = S.size();
 
    // Length of string T
    int M = T.size();
 
    // Prints the count of
    // operations required
    minLength(S, T, N, M);
}

Java

// Java program for the above approach
import java.io.*;
import java.util.*;
 
class GFG{
 
// Function to minimize length of
// string S after removing all
// occurrences of string T as substring
static void minLength(String S, String T, 
                      int N, int M)
{
    String temp = "";
     
    // Count of characters
    // required to be removed
    int subtract = 0;
 
    // Iterate over the string
    for(int i = 0; i < N; ++i) 
    {
         
        // Insert the current
        // character to temp
        temp += S.charAt(i);
 
        // Check if the last M
        // characters forms t or not
        if (temp.length() >= M) 
        {
             
            // Getting the last M characters. 
            // If they are equal to t then
            // remove the last M characters 
            // from the temp string
            if (T.equals(
                temp.substring(temp.length() - M,
                               temp.length()))) 
            {
                 
                // Incrementing subtract by M
                subtract += M;
 
                // Removing last M
                // characters from the
                // string
                int cnt = 0;
                while (cnt != M) 
                {
                    temp = temp.substring(
                        0, temp.length() - 1);
                    ++cnt;
                }
            }
        }
    }
     
    // Print the final answer
    System.out.println((N - subtract));
}
 
// Driver Code
public static void main(String[] args)
{
     
    // Given string S & T
    String S = "aabcbcbd", T = "abc";
     
    // Length of string S
    int N = S.length();
 
    // Length of string T
    int M = T.length();
 
    // Prints the count of
    // operations required
    minLength(S, T, N, M);
}
}
 
// This code is contributed by Dharanendra L V

Python3

# Python program for the above approach
 
# Function to minimize length of
# string S after removing all
# occurrences of string T as substring
def minLength(S, T, N, M):
    temp = "";
 
    # Count of characters
    # required to be removed
    subtract = 0;
 
    # Iterate over the string
    for i in range(N):
 
        # Insert the current
        # character to temp
        temp += S[i];
 
        # Check if the last M
        # characters forms t or not
        if (len(temp) >= M):
 
            # Getting the last M characters.
            # If they are equal to t then
            # remove the last M characters
            # from the temp string
            if (T ==(temp[len(temp) - M: len(temp)])):
 
                # Incrementing subtract by M
                subtract += M;
 
                # Removing last M
                # characters from the
                # string
                cnt = 0;
                while (cnt != M):
                    temp = temp[0: len(temp) - 1];
                    cnt+= 1;
 
    # Print the final answer
    print((N - subtract));
 
# Driver Code
if __name__ == '__main__':
   
    # Given string S & T
    S = "aabcbcbd";
    T = "abc";
 
    # Length of string S
    N = len(S);
 
    # Length of string T
    M = len(T);
 
    # Prints the count of
    # operations required
    minLength(S, T, N, M);
 
# This code is contributed by 29AjayKumar

C#

// C# program for the above approach
using System;
 
class GFG{
 
// Function to minimize length of
// string S after removing all
// occurrences of string T as substring
static void minLength(String S, String T, 
                      int N, int M)
{
    String temp = "";
     
    // Count of characters
    // required to be removed
    int subtract = 0;
 
    // Iterate over the string
    for(int i = 0; i < N; ++i) 
    {
         
        // Insert the current
        // character to temp
        temp += S[i];
 
        // Check if the last M
        // characters forms t or not
        if (temp.Length >= M) 
        {
             
            // Getting the last M characters. 
            // If they are equal to t then
            // remove the last M characters 
            // from the temp string
            if (T.Equals(
                temp.Substring(temp.Length - M, M))) 
            {
                 
                // Incrementing subtract by M
                subtract += M;
 
                // Removing last M
                // characters from the
                // string
                int cnt = 0;
                 
                while (cnt != M) 
                {
                    temp = temp.Substring(
                        0, temp.Length - 1);
                    ++cnt;
                }
            }
        }
    }
     
    // Print the readonly answer
    Console.WriteLine((N - subtract));
}
 
// Driver Code
public static void Main(String[] args)
{
     
    // Given string S & T
    String S = "aabcbcbd", T = "abc";
     
    // Length of string S
    int N = S.Length;
 
    // Length of string T
    int M = T.Length;
 
    // Prints the count of
    // operations required
    minLength(S, T, N, M);
}
}
 
// This code is contributed by shikhasingrajput

Javascript

<script>
 
// Javascript program of the above approach
 
// Function to minimize length of
// string S after removing all
// occurrences of string T as substring
function minLength(S, T,
                      N, M)
{
    let temp = "";
      
    // Count of characters
    // required to be removed
    let subtract = 0;
  
    // Iterate over the string
    for(let i = 0; i < N; ++i)
    {
          
        // Insert the current
        // character to temp
        temp += S[i];
  
        // Check if the last M
        // characters forms t or not
        if (temp.length >= M)
        {
              
            // Getting the last M characters.
            // If they are equal to t then
            // remove the last M characters
            // from the temp string
            if (T == 
                temp.substr(temp.length - M,
                               temp.length))
            {
                  
                // Incrementing subtract by M
                subtract += M;
  
                // Removing last M
                // characters from the
                // string
                let cnt = 0;
                while (cnt != M)
                {
                    temp = temp.substr(
                        0, temp.length - 1);
                    ++cnt;
                }
            }
        }
    }
      
    // Print the final answer
    document.write((N - subtract));
}
 
    // Driver Code
     
      // Given string S & T
    let S = "aabcbcbd", T = "abc";
      
    // Length of string S
    let N = S.length;
  
    // Length of string T
    let M = T.length;
  
    // Prints the count of
    // operations required
    minLength(S, T, N, M);
  
</script>

Output:

Time Complexity: O(N)
Auxiliary Space: O(N)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!