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 contentint 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 codeint 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 npmod = 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 approachlet mod = 1e9 + 7;// Function to return the pairs of subsequences// from S[] and subsequences from T[] such// that both have the same contentfunction 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 codelet S = [1, 1];let n = S.length;let T = [1, 1];let m = T.length;document.write(subsequence(S, T, n, m));</script> |
Output
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 contentint 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 codeint 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); }} |
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 contentfunction 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 codeconst S = [1, 1];const n = S.length;const T = [1, 1];const m = T.length;console.log((subsequence(S, T, n, m) * 2) % mod); |
Output
6
Time Complexity: O(N*M)
Auxiliary Space: O(M)
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!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
