Count of N length Strings having S as a Subsequence
Given a string S and an integer N, the task is to calculate the number of strings of length N consisting of only lowercase characters which have S as one of its subsequences.
Note: As the answer can be very large return it modulo 10^9+7.
Examples:
Input: N = 3, S = “abc”
Output: 1
Explanation: There are only 1 subsequences of length 3 which is “abc”.Input: N = 5, S = “aba”
Output: 6376
Approach: This problem can be solved based on the following observation:
Assume, the length of string S (say X) is less at most N. Then the first occurrence of S in any string must end between [X, N].
- Now, suppose the first occurrence of S ends at index i (where X ≤ i ≤ N), then we can place any character between [i+1, N]. The number of ways to do it is 26N-i.
- Now, the Number of ways to end the first occurrence of string S at ith index is i-1CX-1 * 25i-X * 26N-i because of the following reason:
- If the last character of S is at ith index then X-1 characters must be placed in the first i-1 positions.
- Number of ways to choose X-1 indices to place the first X-1 characters of the string S before ith index is i-1CX-1 .
- So each of the remaining i-X positions can be filled by any of the 25 characters other than the last character of S (because if the last character of S is chosen then the last character of S will be before i which is not consistent with the assumption).Therefore the number of ways for this is 25i-X.
- So, the total number of ways such that S end at ith index is i-1CX-1 * 25i-X * 26N-i.
Follow the steps mentioned below to solve the problem using the above observation:
- Iterate from i = X to N:
- Assume that S is ending at i.
- Calculate the number of possible ways for this as per the above formula.
- Add this to the final count to the answer.
- Return the final answer.
Below is the implementation of the above approach:
C++
// C++ program for Count the number of strings of // length N which have string S as subsequence #include <iostream> using namespace std; // Initialise mod value. const int mod = 1e9 + 7; // Binary exponentiation long long int power( long long int x, long long int y, long long int p) { long long int res = 1; x = x % p; if (x == 0) return 0; while (y > 0) { if (y & 1) { res = (res * x) % p; } y = y >> 1; x = (x * x) % p; } return res; } // Calculate nCr for given n and r long long int nCr( int n, int r, long long int factorials[]) { if (r > n) return 0; long long int answer = factorials[n]; // Divide factorials[r] answer *= power(factorials[r], mod - 2, mod); answer %= mod; // Divide factorials[n-r] answer *= power(factorials[n - r], mod - 2, mod); answer %= mod; return answer; } // Function to count number of possible strings int numberOfStrings( int N, string S) { int X = S.length(); // if N is less than X, then just print 0. if (X > N) { return 0; } // Precalculate factorials long long int factorials[N + 1]; factorials[0] = 1; for ( int i = 1; i <= N; i++) { factorials[i] = factorials[i - 1] * i; factorials[i] %= mod; } // Store answer long long int answer = 0; // Iterate over possible ending // indices for first subsequence of S // in the string for ( int i = X; i <= N; i++) { long long int add = nCr(i - 1, X - 1, factorials); add *= power(26, N - i, mod); add %= mod; add *= power(25, i - X, mod); add %= mod; answer += add; if (answer >= mod) answer -= mod; } return ( int )answer; } // Driver Code int main() { int N = 5; string S = "aba" ; cout << numberOfStrings(N, S); return 0; } |
Java
// Java program for Count the number of strings of // length N which have string S as subsequence import java.io.*; class GFG { // Initialise mod value. static int mod = 1000000007 ; // Binary exponentiation public static long power( long x, long y, long p) { long res = 1 ; x = x % p; if (x == 0 ) return 0 ; while (y > 0 ) { if ((y & 1 ) != 0 ) { res = (res * x) % p; } y = y >> 1 ; x = (x * x) % p; } return res; } // Calculate nCr for given n and r public static long nCr( int n, int r, long factorials[]) { if (r > n) return 0 ; long answer = factorials[n]; // Divide factorials[r] answer *= power(factorials[r], mod - 2 , mod); answer %= mod; // Divide factorials[n-r] answer *= power(factorials[n - r], mod - 2 , mod); answer %= mod; return answer; } // Function to count number of possible strings public static int numberOfStrings( int N, String S) { int X = S.length(); // if N is less than X, then just print 0. if (X > N) { return 0 ; } // Precalculate factorials long factorials[] = new long [N + 1 ]; factorials[ 0 ] = 1 ; for ( int i = 1 ; i <= N; i++) { factorials[i] = factorials[i - 1 ] * i; factorials[i] %= mod; } // Store answer long answer = 0 ; // Iterate over possible ending // indices for first subsequence of S // in the string for ( int i = X; i <= N; i++) { long add = nCr(i - 1 , X - 1 , factorials); add *= power( 26 , N - i, mod); add %= mod; add *= power( 25 , i - X, mod); add %= mod; answer += add; if (answer >= mod) answer -= mod; } return ( int )answer; } public static void main(String[] args) { int N = 5 ; String S = "aba" ; System.out.print(numberOfStrings(N, S)); } } // This code is contributed by Rohit Pradhan. |
Python3
# python3 program for Count the number of strings of # length N which have string S as subsequence # Initialise mod value. mod = int ( 1e9 + 7 ) # Binary exponentiation def power(x, y, p): res = 1 x = x % p if (x = = 0 ): return 0 while (y > 0 ): if (y & 1 ): res = (res * x) % p y = y >> 1 x = (x * x) % p return res # Calculate nCr for given n and r def nCr(n, r, factorials): if (r > n): return 0 answer = factorials[n] # Divide factorials[r] answer * = power(factorials[r], mod - 2 , mod) answer % = mod # Divide factorials[n-r] answer * = power(factorials[n - r], mod - 2 , mod) answer % = mod return answer # Function to count number of possible strings def numberOfStrings(N, S): X = len (S) # if N is less than X, then just print 0. if (X > N): return 0 # Precalculate factorials factorials = [ 0 for _ in range (N + 1 )] factorials[ 0 ] = 1 for i in range ( 1 , N + 1 ): factorials[i] = factorials[i - 1 ] * i factorials[i] % = mod # Store answer answer = 0 # Iterate over possible ending # indices for first subsequence of S # in the string for i in range (X, N + 1 ): add = nCr(i - 1 , X - 1 , factorials) add * = power( 26 , N - i, mod) add % = mod add * = power( 25 , i - X, mod) add % = mod answer + = add if (answer > = mod): answer - = mod return answer # Driver Code if __name__ = = "__main__" : N = 5 S = "aba" print (numberOfStrings(N, S)) # This code is contributed by rakeshsahni |
C#
// C# program to implement above approach using System; class GFG { // Initialise mod value. static int mod = 1000000007; // Binary exponentiation public static long power( long x, long y, long p) { long res = 1; x = x % p; if (x == 0) return 0; while (y > 0) { if ((y & 1) != 0) { res = (res * x) % p; } y = y >> 1; x = (x * x) % p; } return res; } // Calculate nCr for given n and r public static long nCr( int n, int r, long [] factorials) { if (r > n) return 0; long answer = factorials[n]; // Divide factorials[r] answer *= power(factorials[r], mod - 2, mod); answer %= mod; // Divide factorials[n-r] answer *= power(factorials[n - r], mod - 2, mod); answer %= mod; return answer; } // Function to count number of possible strings public static int numberOfStrings( int N, string S) { int X = S.Length; // if N is less than X, then just print 0. if (X > N) { return 0; } // Precalculate factorials long [] factorials = new long [N + 1]; factorials[0] = 1; for ( int i = 1; i <= N; i++) { factorials[i] = factorials[i - 1] * i; factorials[i] %= mod; } // Store answer long answer = 0; // Iterate over possible ending // indices for first subsequence of S // in the string for ( int i = X; i <= N; i++) { long add = nCr(i - 1, X - 1, factorials); add *= power(26, N - i, mod); add %= mod; add *= power(25, i - X, mod); add %= mod; answer += add; if (answer >= mod) answer -= mod; } return ( int )answer; } // Driver Code public static void Main() { int N = 5; string S = "aba" ; Console.Write(numberOfStrings(N, S)); } } // This code is contributed by sanjoy_62. |
Javascript
<script> // JavaScript code for the above approach let mod = 1000000007; function power(x, y, p) { // Initialize result let res = 1; // Update x if it is more // than or equal to p x = x % p; if (x == 0) return 0; while (y > 0) { // If y is odd, multiply // x with result if (y & 1) res = (res * x) % p; // y must be even now // y = $y/2 y = y >> 1; x = (x * x) % p; } return res%p; } function nCr(n, r) { if (r > n) return 0; let answer = 1; for (let i=1 ; i<=r ; i++){ answer *= (n-i+1); answer /= i; } return answer; } // Function to count number of possible strings function numberOfStrings(N, S) { let X = S.length; // if N is less than X, then just print 0. if (X > N) { return 0; } // Store answer let answer = 0; // Iterate over possible ending // indices for first subsequence of S // in the string for (let i = X; i <= N; i++) { let add = nCr(i - 1, X - 1); add *= power(26, N - i, mod); add %= mod; add *= power(25, i - X, mod); add %= mod; answer += add; if (answer >= mod) answer -= mod; } return answer; } // Driver Code let N = 5; let S = "aba" ; document.write(numberOfStrings(N, S)) // This code is contributed by subhamgoyal2014. </script> |
6376
Time Complexity: O(N * logN)
Auxiliary Space: O(N)