Minimize removals to remove another string as a subsequence of a given string

Minimize removals to remove another string as a subsequence of a given string

Given two strings str and X of length N and M respectively, the task is to find the minimum characters required to be removed from the string str such that string str doesn’t contain the string X as a subsequence.

Examples:

Input: str = “btagd”, X = “bad”
Output: 1
Explanation:
String “btag” has does not contain “bad” as a subsequence. Therefore, only one removal is required.

Input: str = “bbaaddd”, X = “bad”
Output: 2

Approach: This problem can be solved by Dynamic Programming. Follow the steps below to solve the problem:

• Traverse the string.
• Initialize a 2D array dp[N][M], where N is the length of string str and M is the length of string X.
• dp[i][j] represents the minimum number of characters removal required in the substring str[0, i] such that there is no occurrence of substring X[0, j] as a subsequence.
• The two transition states are :
  • If str[i] is equal to X[j],  
    • Case 1 : Remove the character str[i]
    • Case 2 : Maintain the character str[i], by ensuring that there is no occurrence of X[0, j-1] as a subsequence in str[0, i]
    •  Update dp[i][j] = min(dp[i − 1][j − 1], dp[i − 1][j] + 1)
  • If str[i] is not equal to X[j], str[i] can be kept as it is.
    •  Update dp[i][j] = dp[i – 1][j]
• Print the minimum removals i.e, dp[N – 1][M – 1]

Below is the implementation of the above approach:

C++

#include <bits/stdc++.h>    using namespace std;    void printMinimumRemovals(string str, string X) {             int N = str.size();             int M = X.size();             int dp[N][M] = {};             for (int j = 0; j < M; j++) {                     if (str[0] == X[j]) {                dp[0][j] = 1;         }     }        for (int i = 1; i < N; i++) {            for (int j = 0; j < M; j++) {                             if (str[i] == X[j]) {                                     dp[i][j] = dp[i - 1][j] + 1;                                     if (j != 0)                     dp[i][j]                         = min(dp[i][j], dp[i - 1][j - 1]);             }                             else {                    dp[i][j] = dp[i - 1][j];             }         }     }                  cout << dp[N - 1][M - 1]; }    int main() {          string str = "btagd";     string X = "bad";                  printMinimumRemovals(str, X);        return 0; }

Time Complexity: O(N * M)
Space Complexity: O(N * M)

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the DSA Self Paced Course at a student-friendly price and become industry ready.

Let's block ads! (Why?)