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 substringvoid 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 Codeint 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 approachimport java.io.*;import java.util.*;class GFG{// Function to minimize length of// string S after removing all// occurrences of string T as substringstatic 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 Codepublic 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 substringdef 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 Codeif __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 approachusing System;class GFG{// Function to minimize length of// string S after removing all// occurrences of string T as substringstatic 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 Codepublic 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 substringfunction 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:
2
Time Complexity: O(N)
Auxiliary Space: O(N)
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
