Find the equal pairs of subsequence of S and subsequence of T
Given two arrays S[] and T[] of size N and M respectively. The task is to find the pairs of subsequences of S[] and subsequences of T[] which are the same in content. Answer could be very large. So, print the answer modulo 109 + 7.
Examples:
Input: S[] = {1, 1}, T[] = {1, 1}
Output: 6
Subsequences of S[] are {}, {1}, {1} and {1, 1}.
Subsequences of T[] are {}, {1}, {1} and {1, 1}.
All the valid pairs are ({}, {}), ({1}, {1}), ({1}, {1}),
({1}, {1}), ({1}, {1}) and ({1, 1}, {1, 1}).
Input: S[] = {1, 3}, T[] = {3, 1}
Output: 3
Approach: Let dp[i][j] be the number of ways to create subsequences only using the first i elements of S[] and the first j elements of T[] such that the subsequences are the same and the ith element of S[] and the jth element of T[] are part of the subsequences.
Basically, dp[i][j] is the answer to the problem if only the first i elements of S[] and the first j elements of T[] are considered. If S[i] != T[j] then dp[i][j] = 0 because no subsequence will end by using the ith element of S[] and the jth element of T[]. If S[i] = T[j] then dp[i][j] = ∑k=1i-1 ∑l=1j-1 dp[k][l] + 1 because the previous index of S[] can be any index ≤ i and the previous index of T[] can be any index ≤ j.
As a base case, dp[0][0] = 1. This represents the case where no element is taken. The runtime of this is O(N2 * M2) but we can speed this up by precomputing the sums.
Let sum[i][j] = ∑k=1i ∑l=1jdp[k][l] which is a 2D prefix sum of the dp array. sum[i][j] = sum[i – 1][j] + sum[i][j – 1] – sum[i – 1][j – 1] + dp[i][j]. With sum[i][j], each state dp[i][j] can now be calculated in O(1).
Since there are N * M states, the runtime will be O(N * M).
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; #define mod (int)(1e9 + 7) // Function to return the pairs of subsequences // from S[] and subsequences from T[] such // that both have the same content int subsequence( int S[], int T[], int n, int m) { // Create dp array int dp[n + 1][m + 1]; // Base values for ( int i = 0; i <= n; i++) dp[i][0] = 1; // Base values for ( int j = 0; j <= m; j++) dp[0][j] = 1; for ( int i = 1; i <= n; ++i) { for ( int j = 1; j <= m; ++j) { // Keep previous dp value dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]; // If both elements are same if (S[i - 1] == T[j - 1]) dp[i][j] += dp[i - 1][j - 1]; dp[i][j] += mod; dp[i][j] %= mod; } } // Return the required answer return dp[n][m]; } // Driver code int main() { int S[] = { 1, 1 }; int n = sizeof (S) / sizeof (S[0]); int T[] = { 1, 1 }; int m = sizeof (T) / sizeof (T[0]); cout << subsequence(S, T, n, m); return 0; } |
Java
// Java implementation of the approach import java.util.*; class GFG { // Function to return the pairs of subsequences // from S[] and subsequences from T[] such // that both have the same content static int subsequence( int [] S, int [] T, int n, int m) { // Create dp array int [][] dp = new int [n + 1 ][m + 1 ]; int mod = 1000000007 ; // Base values for ( int i = 0 ; i <= n; i++) dp[i][ 0 ] = 1 ; // Base values for ( int j = 0 ; j <= m; j++) dp[ 0 ][j] = 1 ; for ( int i = 1 ; i <= n; ++i) { for ( int j = 1 ; j <= m; ++j) { // Keep previous dp value dp[i][j] = dp[i - 1 ][j] + dp[i][j - 1 ] - dp[i - 1 ][j - 1 ]; // If both elements are same if (S[i - 1 ] == T[j - 1 ]) dp[i][j] += dp[i - 1 ][j - 1 ]; dp[i][j] += mod; dp[i][j] %= mod; } } // Return the required answer return dp[n][m]; } // Driver code public static void main(String []args) { int S[] = { 1 , 1 }; int n = S.length; int T[] = { 1 , 1 }; int m = T.length; System.out.println(subsequence(S, T, n, m)); } } // This code is contributed by Sanjit Prasad |
Python3
# Python3 implementation of the approach import numpy as np mod = int ( 1e9 + 7 ) # Function to return the pairs of subsequences # from S[] and subsequences from T[] such # that both have the same content def subsequence(S, T, n, m) : # Create dp array dp = np.zeros((n + 1 , m + 1 )); # Base values for i in range (n + 1 ) : dp[i][ 0 ] = 1 ; # Base values for j in range (m + 1 ) : dp[ 0 ][j] = 1 ; for i in range ( 1 , n + 1 ) : for j in range ( 1 , m + 1 ) : # Keep previous dp value dp[i][j] = dp[i - 1 ][j] + dp[i][j - 1 ] - \ dp[i - 1 ][j - 1 ]; # If both elements are same if (S[i - 1 ] = = T[j - 1 ]) : dp[i][j] + = dp[i - 1 ][j - 1 ]; dp[i][j] + = mod; dp[i][j] % = mod; # Return the required answer return dp[n][m]; # Driver code if __name__ = = "__main__" : S = [ 1 , 1 ]; n = len (S); T = [ 1 , 1 ]; m = len (T); print (subsequence(S, T, n, m)); # This code is contributed by kanugargng |
C#
// C# implementation of the approach using System; class GFG { // Function to return the pairs of subsequences // from S[] and subsequences from T[] such // that both have the same content static int subsequence( int [] S, int [] T, int n, int m) { // Create dp array int [,] dp = new int [n + 1, m + 1]; int mod = 1000000007; // Base values for ( int i = 0; i <= n; i++) dp[i, 0] = 1; // Base values for ( int j = 0; j <= m; j++) dp[0, j] = 1; for ( int i = 1; i <= n; ++i) { for ( int j = 1; j <= m; ++j) { // Keep previous dp value dp[i, j] = dp[i - 1, j] + dp[i, j - 1] - dp[i - 1, j - 1]; // If both elements are same if (S[i - 1] == T[j - 1]) dp[i, j] += dp[i - 1, j - 1]; dp[i, j] += mod; dp[i, j] %= mod; } } // Return the required answer return dp[n, m]; } // Driver code public static void Main() { int []S = { 1, 1 }; int n = S.Length; int []T = { 1, 1 }; int m = T.Length; Console.WriteLine(subsequence(S, T, n, m)); } } // This code is contributed by AnkitRai01 |
Javascript
<script> // JavaScript implementation of the approach let mod = 1e9 + 7; // Function to return the pairs of subsequences // from S[] and subsequences from T[] such // that both have the same content function subsequence(S, T, n, m) { // Create dp array let dp = new Array() for (let i = 0; i < n + 1; i++) { let temp = []; for (let j = 0; j < m + 1; j++) { temp.push([]) } dp.push(temp) } // Base values for (let i = 0; i <= n; i++) dp[i][0] = 1; // Base values for (let j = 0; j <= m; j++) dp[0][j] = 1; for (let i = 1; i <= n; ++i) { for (let j = 1; j <= m; ++j) { // Keep previous dp value dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]; // If both elements are same if (S[i - 1] == T[j - 1]) dp[i][j] += dp[i - 1][j - 1]; dp[i][j] += mod; dp[i][j] %= mod; } } // Return the required answer return dp[n][m]; } // Driver code let S = [1, 1]; let n = S.length; let T = [1, 1]; let m = T.length; document.write(subsequence(S, T, n, m)); </script> |
6
Time Complexity: O( N*M )
Auxiliary Space: O(N*M )
Efficient approach : Space optimization
In previous approach the current value dp[i][j] is only depend upon the current and previous row values of DP. So to optimize the space complexity we use a single 1D array to store the computations.
Implementation steps:
- Create a 1D vector dp of size M+1.
- Set a base case by initializing the value of DP ( dp[0] = 1 ).
- Now iterate over subproblems by the help of nested loop and get the current value from previous computations.
- Now Create a variable prev used to store the previous value and temp to store current valueof DP vector .
- After every iteration assign the value of temp to prev for further iteration.
- At last return and print the final answer stored in dp[m].
Implementation:
C++
// C++ code for above approach #include <bits/stdc++.h> using namespace std; #define mod (int)(1e9 + 7) // Function to return the pairs of subsequences // from S[] and subsequences from T[] such // that both have the same content int subsequence( int S[], int T[], int n, int m) { // Create dp vector vector< int > dp(m + 1); // Base values dp[0] = 1; for ( int i = 1; i <= n; ++i) { int prev = 1; for ( int j = 1; j <= m; ++j) { int temp = dp[j]; dp[j] = dp[j] + dp[j - 1] - prev; if (S[i - 1] == T[j - 1]) { dp[j] = dp[j] + prev; } dp[j] += mod; dp[j] %= mod; prev = temp; } } // Return the required answer return dp[m]; } // Driver code int main() { int S[] = { 1, 1 }; int n = sizeof (S) / sizeof (S[0]); int T[] = { 1, 1 }; int m = sizeof (T) / sizeof (T[0]); cout << subsequence(S, T, n, m) * 2 % mod; return 0; } |
Java
import java.util.Arrays; public class GFG { static final int mod = ( int ) 1e9 + 7 ; // Function to return the pairs of subsequences // from S[] and subsequences from T[] such // that both have the same content static int subsequence( int [] S, int [] T, int n, int m) { // Create dp array to store the number of ways to form subsequences from T int [] dp = new int [m + 1 ]; // Base values dp[ 0 ] = 1 ; // There is always an empty subsequence in any sequence for ( int i = 1 ; i <= n; i++) { int prev = 1 ; // Store the previous value of dp[j] for ( int j = 1 ; j <= m; j++) { int temp = dp[j]; // Store the current value of dp[j] to use in the next iteration dp[j] = dp[j] + dp[j - 1 ] - prev; if (S[i - 1 ] == T[j - 1 ]) { dp[j] = dp[j] + prev; // If the elements match, add the previous value of dp[j] } dp[j] += mod; // Ensure dp[j] is non-negative dp[j] %= mod; // Take the modulo to prevent overflow prev = temp; // Update prev for the next iteration } } // Return the required answer return dp[m]; } // Driver code public static void main(String[] args) { int [] S = { 1 , 1 }; int n = S.length; int [] T = { 1 , 1 }; int m = T.length; // Print the result System.out.println(subsequence(S, T, n, m) * 2 % mod); } } |
Python3
# Python code for above approach # Function to return the pairs of subsequences # from S[] and subsequences from T[] such # that both have the same content def subsequence(S, T, n, m): mod = ( 10 * * 9 ) + 7 # Create dp list dp = [ 0 ] * (m + 1 ) # Base values dp[ 0 ] = 1 for i in range ( 1 , n + 1 ): prev = 1 for j in range ( 1 , m + 1 ): temp = dp[j] dp[j] = (dp[j] + dp[j - 1 ] - prev) % mod if S[i - 1 ] = = T[j - 1 ]: dp[j] = (dp[j] + prev) % mod prev = temp # Return the required answer return dp[m] # Driver code S = [ 1 , 1 ] n = len (S) T = [ 1 , 1 ] m = len (T) print ((subsequence(S, T, n, m) * 2 ) % ( 10 * * 9 + 7 )) # This code is contributed by Susobhan Akhuli |
C#
using System; public class GFG { const int mod = 1000000007; // Value of mod constant // Function to return the pairs of subsequences // from S[] and subsequences from T[] such // that both have the same content public static int Subsequence( int [] S, int [] T, int n, int m) { // Create dp array to store the number of valid pairs int [] dp = new int [m + 1]; // Base values dp[0] = 1; // Dynamic Programming: Fill the dp array for ( int i = 1; i <= n; ++i) { int prev = 1; for ( int j = 1; j <= m; ++j) { // Store the current value of dp[j] in temp int temp = dp[j]; // Calculate the new value of dp[j] using the recurrence relation dp[j] = (dp[j] + dp[j - 1] - prev + mod) % mod; // Check if the elements at positions i-1 in S and j-1 in T are equal if (S[i - 1] == T[j - 1]) { // If they are equal, add the previous value (prev) to dp[j] dp[j] = (dp[j] + prev) % mod; } // Update prev for the next iteration prev = temp; } } // Return the required answer return dp[m]; } public static void Main( string [] args) { int [] S = { 1, 1 }; int n = S.Length; int [] T = { 1, 1 }; int m = T.Length; // Calculate the number of pairs of subsequences with the same content // and print the result, multiplied by 2 and then taken modulo mod Console.WriteLine(Subsequence(S, T, n, m) * 2 % mod); } } |
Javascript
const mod = 1e9 + 7; // Function to return the pairs of subsequences // from S[] and subsequences from T[] such // that both have the same content function subsequence(S, T, n, m) { // Create dp array const dp = new Array(m + 1).fill(0); // Base values dp[0] = 1; for (let i = 1; i <= n; ++i) { let prev = 1; for (let j = 1; j <= m; ++j) { const temp = dp[j]; dp[j] = dp[j] + dp[j - 1] - prev; if (S[i - 1] === T[j - 1]) { dp[j] = dp[j] + prev; } dp[j] += mod; dp[j] %= mod; prev = temp; } } // Return the required answer return dp[m]; } // Driver code const S = [1, 1]; const n = S.length; const T = [1, 1]; const m = T.length; console.log((subsequence(S, T, n, m) * 2) % mod); |
6
Time Complexity: O(N*M)
Auxiliary Space: O(M)