Given an integer N and string S of size M, the task is to find the number of ways of forming string of length N such that it is possible to rearrange the string to have S as substring. Print the answer modulo 109 + 7.
Note: All characters of string S are distinct.
Examples:
Input: N = 3, S = “abc”
Output: 6
Explanation: There are 6 strings that can be rearranged to have string S as substring: Those strings are “abc”, “acb”, “bac”, “bca”, “cab” and “cba”.Input: N = 4, S = “abc”
Output: 588
Explanation: Some possible strings from 588 strings are “bcaz”, “zabc”, “abcc” and “abbc” whose characters can be rearranged to have “abc” as substring.
Approach: Implement the idea below to solve the problem
Bitmask Dynamic Programming can be used to solve this problem. We can maintain dp[i][j] stores the number of ways to have string S as the substring if we are at index i with submask j. The submask stores which characters we have already taken into our string. If submask j has 0th bit as set then it means that character at index 0 of string S is already present in our string. At any index i, we have 2 choices:
- Choice 1: Choose any character from string S to be placed at index i.
- Choice 2: Choose any character which is not present in string S to be placed at index i.
Explore all the choices to get the final answer.
Steps to solve the problem:
- Define a recursive function, say countOfArr(idx, bitmask) which returns the number of ways to have string S as a substring if we are at index idx and have selected characters represented by bitmask.
- If we have iterated through the whole string, the check if our string has all the characters which are present in S by comparing the submask. If yes, return 1 else return 0.
- If we are at any other index, iterate over all the characters of string S and place every character at index idx.
- Also place all those characters which are not present in string S at index idx.
- Count all the choices to get the final answer.
Code to implement the approach:
C++
#include <bits/stdc++.h>using namespace std;const int MOD = 1e9 + 7;// to avoid interger overflow#define int long long// Function to find ways to form N sized string which has// string S as substring after rearranging formed stringint countOfArr(int idx, int bitmask, string& S, int N, int M, vector<vector<int> >& dp){ // base case if (idx == N) { return bitmask == ((1 << M) - 1); } if (dp[idx][bitmask] != -1) return dp[idx][bitmask]; int ans = 0; // Choose any one character of string S to be placed at // index i for (int i = 0; i < M; i++) { ans += countOfArr(idx + 1, bitmask | (1LL << i), S, N, M, dp); ans %= MOD; } // Choose a character which is not present in string S // to be placed at index i ans += ((26 - M) * countOfArr(idx + 1, bitmask, S, N, M, dp)) % MOD; // returning final answer return dp[idx][bitmask] = ans;}// Driver Codeint32_t main(){ // Input int N = 4, M = 3; string S = "abc"; // DP array initalized with -1 vector<vector<int> > dp(N + 1, vector<int>((1 << M), -1)); int bitmask = 0; // Function Call cout << countOfArr(0, bitmask, S, N, M, dp) << endl; return 0;} |
Java
import java.util.Arrays; class GFG{ static final int MOD = 1000000007; // Function to find ways to form N sized // string which has string S as substring // after rearranging formed string static int countOfArr(int idx, int bitmask, String S, int N, int M, int[][] dp) { // base case if (idx == N) { return bitmask == ((1 << M) - 1) ? 1 : 0; } if (dp[idx][bitmask] != -1) return dp[idx][bitmask]; int ans = 0; // Choose any one character of string S // to be placed at index i for (int i = 0; i < M; i++) { ans += countOfArr(idx + 1, bitmask | (1 << i), S, N, M, dp); ans %= MOD; } // Choose a character which is not present // in string S to be placed at index i ans += ((26 - M) * countOfArr(idx + 1, bitmask, S, N, M, dp)) % MOD; // returning final answer return dp[idx][bitmask] = ans; } // Driver Code public static void main(String[] args) { // Input int N = 4, M = 3; String S = "abc"; // DP array initalized with -1 int[][] dp = new int[N + 1][(1 << M)]; for (int[] row : dp) { Arrays.fill(row, -1); } int bitmask = 0; // Function Call System.out.println(countOfArr(0, bitmask, S, N, M, dp)); }} |
Python3
MOD = 10**9 + 7# Function to find ways to form N sized string which has# string S as substring after rearranging formed stringdef countOfArr(idx, bitmask, S, N, M, dp): # Base case if idx == N: return bitmask == ((1 << M) - 1) if dp[idx][bitmask] != -1: return dp[idx][bitmask] ans = 0 # Choose any one character of string S to be placed at # index i for i in range(M): ans += countOfArr(idx + 1, bitmask | (1 << i), S, N, M, dp) ans %= MOD # Choose a character which is not present in string S # to be placed at index i ans += ((26 - M) * countOfArr(idx + 1, bitmask, S, N, M, dp)) % MOD # returning final answer dp[idx][bitmask] = ans return ans# Driver Codeif __name__ == "__main__": # Input N = 4 M = 3 S = "abc" # DP array initialized with -1 dp = [[-1 for _ in range(1 << M)] for _ in range(N + 1)] bitmask = 0 # Function Call print(countOfArr(0, bitmask, S, N, M, dp)) |
Javascript
const MOD = 1e9 + 7;function GFG(idx, bitmask, S, N, M, dp) { // base case if (idx === N) { return bitmask === (1 << M) - 1 ? 1 : 0; } if (dp[idx][bitmask] !== -1) { return dp[idx][bitmask]; } let ans = 0; // Choose any one character of the string S to be placed at index i for (let i = 0; i < M; i++) { ans += GFG(idx + 1, bitmask | (1 << i), S, N, M, dp); ans %= MOD; } // Choose a character which is not present in string S to be placed at index i ans += ((26 - M) * GFG(idx + 1, bitmask, S, N, M, dp)) % MOD; // returning final answer dp[idx][bitmask] = ans; return ans;}// Driver Codefunction main() { // Input let N = 4; let M = 3; let S = "abc"; let dp = new Array(N + 1).fill(0).map(() => new Array(1 << M).fill(-1)); let bitmask = 0; // Function Call console.log(GFG(0, bitmask, S, N, M, dp));}main(); |
588
Time Complexity: O( N * 2M), where N is the length of string we have to make and M is the length of input string S.
Auxiliary Space: O(N * 2M)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
