Tutorialspoint.dev

Ways of transforming one string to other by removing 0 or more characters

Given two sequences A, B, find out number of unique ways in sequence A, to form a subsequence of A that is identical to the sequence B. Transformation is meant by converting string A (by removing 0 or more characters) to string B.

Examples:

Input : A = "abcccdf", B = "abccdf"
Output : 3
Explanation : Three ways will be -> "ab.ccdf", 
"abc.cdf" & "abcc.df" .
"." is where character is removed. 

Input : A = "aabba", B = "ab"
Output : 4
Expalnation : Four ways will be -> "a.b..",
 "a..b.", ".ab.." & ".a.b." .
"." is where characters are removed.

Asked in :



The idea to solve this problem is using Dynamic Programming. Construct a 2D DP matrix of m*n size, where m is size of string B and n is size of string A.
dp[i][j] gives the number of ways of transforming string A[0…j] to B[0…i].

  • Case 1 : dp[0][j] = 1, since placing B = “” with any substring of A would have only 1 solution which is to delete all characters in A.
  • Case 2 : when i > 0, dp[i][j] can be derived by two cases:
    • Case 2.a : if B[i] != A[j], then the solution would be to ignore the character A[j] and align substring B[0..i] with A[0..(j-1)]. Therefore, dp[i][j] = dp[i][j-1].
    • Case 2.b : if B[i] == A[j], then first we could have the solution in case a), but also we could match the characters B[i] and A[j] and place the rest of them (i.e. B[0..(i-1)] and A[0..(j-1)]. As a result, dp[i][j] = dp[i][j-1] + dp[i-1][j-1].
  • C++

    // C++ program to count the distinct transformation
    // of one string to other.
    #include <bits/stdc++.h>
    using namespace std;
      
    int countTransformation(string a, string b)
    {
        int n = a.size(), m = b.size();
      
        // If b = "" i.e., an empty string. There
        // is only one way to transform (remove all
        // characters)
        if (m == 0)
            return 1;
      
        int dp[m + 1][n + 1];
        memset(dp, 0, sizeof(dp));
      
        // Fil dp[][] in bottom up manner
        // Traverse all character of b[]
        for (int i = 0; i < m; i++) {
      
            // Traverse all charaters of a[] for b[i]
            for (int j = i; j < n; j++) {
      
                // Filling the first row of the dp
                // matrix.
                if (i == 0) {
                    if (a[j] == b[i] && j == 0)
                        dp[i][j] = 1;
                    else if (a[j] == b[i])
                        dp[i][j] = dp[i][j - 1] + 1;
                    else
                        dp[i][j] = dp[i][j - 1];
                }
      
                // Filling other rows.
                else {
                    if (a[j] == b[i])
                        dp[i][j] = dp[i][j - 1] + 
                                   dp[i - 1][j - 1];
                    else
                        dp[i][j] = dp[i][j - 1];
                }
            }
        }
      
        return dp[m - 1][n - 1];
    }
      
    // Driver code
    int main()
    {
        string a = "abcccdf", b = "abccdf";
        cout << countTransformation(a, b) << endl;
        return 0;
    }

    Java

    // Java program to count the
    // distinct transformation
    // of one string to other.
    class GFG 
    {
      
        static int countTransformation(String a,
                                       String b) 
        {
            int n = a.length(), m = b.length();
      
            // If b = "" i.e., an empty string. There
            // is only one way to transform (remove all
            // characters)
            if (m == 0
            {
                return 1;
            }
      
            int dp[][] = new int[m + 1][n + 1];
      
            // Fil dp[][] in bottom up manner
            // Traverse all character of b[]
            for (int i = 0; i < m; i++)
            {
      
                // Traverse all charaters of a[] for b[i]
                for (int j = i; j < n; j++) 
                {
      
                    // Filling the first row of the dp
                    // matrix.
                    if (i == 0)
                    {
                        if (a.charAt(j) == b.charAt(i) &&
                                                j == 0)
                        {
                            dp[i][j] = 1;
                        }
                        else if (a.charAt(j) == b.charAt(i)) 
                        {
                            dp[i][j] = dp[i][j - 1] + 1;
                        
                        else 
                        {
                            dp[i][j] = dp[i][j - 1];
                        }
                    }
                      
                    // Filling other rows.
                    else if (a.charAt(j) == b.charAt(i)) 
                    {
                        dp[i][j] = dp[i][j - 1]
                                + dp[i - 1][j - 1];
                    
                    else
                    {
                        dp[i][j] = dp[i][j - 1];
                    }
                }
            }
            return dp[m - 1][n - 1];
        }
      
        // Driver code
        public static void main(String[] args)
        {
            String a = "abcccdf", b = "abccdf";
            System.out.println(countTransformation(a, b));
        }
    }
      
    // This code is contributed by
    // PrinciRaj1992

    Python3

    # Python3 program to count the distinct
    # transformation of one string to other.

    def countTransformation(a, b):
    n = len(a)
    m = len(b)

    # If b = “” i.e., an empty string. There
    # is only one way to transform (remove all
    # characters)
    if m == 0:
    return 1

    dp = [[0] * (n + 1) for _ in range(m + 1)]

    # Fill dp[][] in bottom up manner
    # Traverse all character of b[]
    for i in range(m):

    # Traverse all charaters of a[] for b[i]
    for j in range(i, n):

    # Filling the first row of the dp
    # matrix.
    if i == 0:
    if a[j] == b[i] and j == 0:
    dp[i][j] = 1
    elif a[j] == b[i]:
    dp[i][j] = dp[i][j – 1] + 1
    else:
    dp[i][j] = dp[i][j – 1]

    # Filling other rows
    else:
    if a[j] == b[i]:
    dp[i][j] = (dp[i][j – 1] +
    dp[i – 1][j – 1])
    else:
    dp[i][j] = dp[i][j – 1]
    return dp[m – 1][n – 1]

    # Driver Code
    if __name__ == “__main__”:
    a = “abcccdf”
    b = “abccdf”
    print(countTransformation(a, b))

    # This code is contributed by vibhu4agarwal

    C#

    // C# program to count the distinct transformation 
    // of one string to other. 
    using System; 
      
    class GFG 
        static int countTransformation(string a, string b) 
        
            int n = a.Length, m = b.Length; 
          
            // If b = "" i.e., an empty string. There 
            // is only one way to transform (remove all 
            // characters) 
            if (m == 0) 
                return 1; 
          
            int[,] dp = new int[m + 1, n + 1]; 
            for(int i = 0; i < m + 1; i++)
                for(int j = 0; j < n + 1; j++)
                    dp[i, j] = 0;
          
            // Fil dp[][] in bottom up manner 
            // Traverse all character of b[] 
            for (int i = 0; i < m; i++)
            
          
                // Traverse all charaters of a[] for b[i] 
                for (int j = i; j < n; j++) 
                
          
                    // Filling the first row of the dp 
                    // matrix. 
                    if (i == 0) 
                    
                        if (a[j] == b[i] && j == 0) 
                            dp[i, j] = 1; 
                        else if (a[j] == b[i]) 
                            dp[i, j] = dp[i, j - 1] + 1; 
                        else
                            dp[i, j] = dp[i, j - 1]; 
                    }  
          
                    // Filling other rows. 
                    else 
                    
                        if (a[j] == b[i]) 
                            dp[i, j] = dp[i, j - 1] + 
                                    dp[i - 1, j - 1]; 
                        else
                            dp[i, j] = dp[i, j - 1]; 
                    
                
            
            return dp[m - 1, n - 1]; 
        
          
        // Driver code 
        static void Main() 
        
            string a = "abcccdf", b = "abccdf"
            Console.Write(countTransformation(a, b)); 
        }
    }
      
    // This code is contributed by DrRoot_

    Output:

    3
    

    Time Complexity: O(n^2)

    Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter