Given a string S and an integer K, the task is to find the total number of strings that can be formed by inserting exactly K characters at any position of the string S. Since the answer can be large, print it modulo 109+7.
Examples:
Input: S = “a” K = 1
Output: 51
Explanation:
Since any of the 26 characters can be inserted at before ‘a’ or after ‘a’, a total of 52 possible strings can be formed.
But the string “aa” gets formed twice. Hence count of distinct strings possible is 51.
Input: S = “abc” K = 2
Output: 6376
Approach:
The idea is to find the number of strings that contains the str as a subsequence. Follow the steps below to solve the problem:
- The total number of strings that can be formed by N characters is 26N.
- Calculate 26N using Binary Exponentiation.
- In this problem, only the strings that contain the str as a subsequence needs to be considered.
- Hence, the final count of strings is given by
(total number of strings) – (number of strings that don’t contain the input string as a sub-sequence)
- While calculating such strings that don’t contain the str as a subsequence, observe that the length of the prefix of S is a subsequence of the resulting string can be between 0 to |S|-1.
- For every prefix length from 0 to |S|-1, find the total number of strings that can be formed with such a prefix as a sub-sequence. Then subtract that value from 26N.
- Hence, the final answer is:
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;#define int long long intconst int mod = 1e9 + 7;// Function to calculate and return// x^n in log(n) time using// Binary Exponentiationint binExp(int base, int power){ int x = 1; while (power) { if (power % 2 == 1) x = ((x % mod) * (base % mod)) % mod; base = ((base % mod) * (base % mod)) % mod; power = power / 2; } return x;}// Function to calculate the factorial// of a numberint fact(int num){ int result = 1; for (int i = 1; i <= num; ++i) { result = ((result % mod) * (i % mod)) % mod; } return result;}// Function to calculate combinationint calculate_nCi(int N, int i){ // nCi = ( n! ) / (( n-i )! * i!) int nfact = fact(N); int ifact = fact(i); int dfact = fact(N - i); // Using Euler's theorem of Modular // multiplicative inverse to find // the inverse of a number. // (1/a)%mod=a^(m?2)%mod int inv_ifact = binExp(ifact, mod - 2); int inv_dfact = binExp(dfact, mod - 2); int denm = ((inv_ifact % mod) * (inv_dfact % mod)) % mod; int answer = ((nfact % mod) * (denm % mod)) % mod; return answer;}// Function to find the count of// possible stringsvoid countSubstring(int N, int s, int k){ // Number of ways to form all // possible strings int allWays = binExp(26, N); // Number of ways to form strings // that don't contain the input // string as a subsequence int noWays = 0; // Checking for all prefix length // from 0 to |S|-1. for (int i = 0; i < s; ++i) { // to calculate nCi int nCi = calculate_nCi(N, i); // Select the remaining characters // 25 ^ (N-i) int remaining = binExp(25, N - i); int multiply = ((nCi % mod) * (remaining % mod)) % mod; // Add the answer for this prefix // length to the final answer noWays = ((noWays % mod) + (multiply % mod)) % mod; } // Answer is the difference of // allWays and noWays int answer = ((allWays % mod) - (noWays % mod)) % mod; if (answer < 0) answer += mod; // Print the answer cout << answer;}// Driver Codeint32_t main(){ string str = "abc"; int k = 2; int s = str.length(); int N = s + k; countSubstring(N, s, k);} |
Java
// Java program for the above approachclass GFG{static final long mod = 1000000007;// Function to calculate and return// x^n in log(n) time using// Binary Exponentiationstatic long binExp(long base, long power){ long x = 1; while (power != 0) { if (power % 2 == 1) x = ((x % mod) * (base % mod)) % mod; base = ((base % mod) * (base % mod)) % mod; power = power / 2; } return x;}// Function to calculate the factorial// of a numberstatic long fact(long num){ long result = 1; for(long i = 1; i <= num; ++i) { result = ((result % mod) * (i % mod)) % mod; } return result;}// Function to calculate combinationstatic long calculate_nCi(long N, long i){ // nCi = ( n! ) / (( n-i )! * i!) long nfact = fact(N); long ifact = fact(i); long dfact = fact(N - i); // Using Euler's theorem of Modular // multiplicative inverse to find // the inverse of a number. // (1/a)%mod=a^(m?2)%mod long inv_ifact = binExp(ifact, mod - 2); long inv_dfact = binExp(dfact, mod - 2); long denm = ((inv_ifact % mod) * (inv_dfact % mod)) % mod; long answer = ((nfact % mod) * (denm % mod)) % mod; return answer;}// Function to find the count of// possible stringsstatic void countSubstring(long N, long s, long k){ // Number of ways to form all // possible strings long allWays = binExp(26, N); // Number of ways to form strings // that don't contain the input // string as a subsequence long noWays = 0; // Checking for all prefix length // from 0 to |S|-1. for(long i = 0; i < s; ++i) { // To calculate nCi long nCi = calculate_nCi(N, i); // Select the remaining characters // 25 ^ (N-i) long remaining = binExp(25, N - i); long multiply = ((nCi % mod) * (remaining % mod)) % mod; // Add the answer for this prefix // length to the final answer noWays = ((noWays % mod) + (multiply % mod)) % mod; } // Answer is the difference of // allWays and noWays long answer = ((allWays % mod) - (noWays % mod)) % mod; if (answer < 0) answer += mod; // Print the answer System.out.println(answer);} // Driver code public static void main(String[] args) { String str = "abc"; long k = 2; long s = str.length(); long N = s + k; countSubstring(N, s, k);}}// This code is contributed by rutvik_56 |
Python3
# Python3 program for the above approachmod = 1000000007# Function to calculate and return# x^n in log(n) time using# Binary Exponentiationdef binExp(base, power): x = 1 while (power): if (power % 2 == 1): x = (((x % mod) * (base % mod)) % mod) base = (((base % mod) * (base % mod)) % mod) power = power // 2 return x# Function to calculate the factorial# of a numberdef fact(num): result = 1 for i in range(1, num + 1): result = (((result % mod) * (i % mod)) % mod) return result# Function to calculate combinationdef calculate_nCi(N, i): # nCi = ( n! ) / (( n-i )! * i!) nfact = fact(N) ifact = fact(i) dfact = fact(N - i) # Using Euler's theorem of Modular # multiplicative inverse to find # the inverse of a number. # (1/a)%mod=a^(m?2)%mod inv_ifact = binExp(ifact, mod - 2) inv_dfact = binExp(dfact, mod - 2) denm = (((inv_ifact % mod) * (inv_dfact % mod)) % mod) answer = (((nfact % mod) * (denm % mod)) % mod) return answer# Function to find the count of# possible stringsdef countSubstring(N, s, k): # Number of ways to form all # possible strings allWays = binExp(26, N) # Number of ways to form strings # that don't contain the input # string as a subsequence noWays = 0 # Checking for all prefix length # from 0 to |S|-1. for i in range(s): # To calculate nCi nCi = calculate_nCi(N, i) # Select the remaining characters # 25 ^ (N-i) remaining = binExp(25, N - i) multiply = (((nCi % mod) * (remaining % mod)) % mod) # Add the answer for this prefix # length to the final answer noWays =(((noWays % mod) + (multiply % mod)) % mod) # Answer is the difference of # allWays and noWays answer = (((allWays % mod) - (noWays % mod)) % mod) if (answer < 0): answer += mod # Print the answer print(answer)# Driver Codeif __name__ == "__main__": st = "abc" k = 2 s = len(st) N = s + k countSubstring(N, s, k)# This code is contributed by chitranayal |
C#
// C# program for the above approachusing System;class GFG{static readonly long mod = 1000000007;// Function to calculate and return// x^n in log(n) time using// Binary Exponentiationstatic long binExp(long Base, long power){ long x = 1; while (power != 0) { if (power % 2 == 1) x = ((x % mod) * (Base % mod)) % mod; Base = ((Base % mod) * (Base % mod)) % mod; power = power / 2; } return x;}// Function to calculate the factorial// of a numberstatic long fact(long num){ long result = 1; for(long i = 1; i <= num; ++i) { result = ((result % mod) * (i % mod)) % mod; } return result;}// Function to calculate combinationstatic long calculate_nCi(long N, long i){ // nCi = ( n! ) / (( n-i )! * i!) long nfact = fact(N); long ifact = fact(i); long dfact = fact(N - i); // Using Euler's theorem of Modular // multiplicative inverse to find // the inverse of a number. // (1/a)%mod=a^(m?2)%mod long inv_ifact = binExp(ifact, mod - 2); long inv_dfact = binExp(dfact, mod - 2); long denm = ((inv_ifact % mod) * (inv_dfact % mod)) % mod; long answer = ((nfact % mod) * (denm % mod)) % mod; return answer;}// Function to find the count of// possible stringsstatic void countSubstring(long N, long s, long k){ // Number of ways to form all // possible strings long allWays = binExp(26, N); // Number of ways to form strings // that don't contain the input // string as a subsequence long noWays = 0; // Checking for all prefix length // from 0 to |S|-1. for(long i = 0; i < s; ++i) { // To calculate nCi long nCi = calculate_nCi(N, i); // Select the remaining characters // 25 ^ (N-i) long remaining = binExp(25, N - i); long multiply = ((nCi % mod) * (remaining % mod)) % mod; // Add the answer for this prefix // length to the readonly answer noWays = ((noWays % mod) + (multiply % mod)) % mod; } // Answer is the difference of // allWays and noWays long answer = ((allWays % mod) - (noWays % mod)) % mod; if (answer < 0) answer += mod; // Print the answer Console.WriteLine(answer);} // Driver code public static void Main(String[] args) { String str = "abc"; long k = 2; long s = str.Length; long N = s + k; countSubstring(N, s, k);}}// This code is contributed by Rajput-Ji |
Javascript
<script>// JavaScript program for the above approach var mod = 10007; // Function to calculate and return // x^n in log(n) time using // Binary Exponentiation function binExp(base , power) { var x = 1; while (power != 0) { if (power % 2 == 1) x = (((x % mod) * (base % mod)) % mod); base = (((base % mod) * (base % mod)) % mod); power = parseInt(power / 2); } return x; } // Function to calculate the factorial // of a number function fact(num) { var result = 1; for (var i = 1; i <= num; ++i) { result = (((result % mod) * (i % mod)) % mod); } return result; } // Function to calculate combination function calculate_nCi(N , i) { // nCi = ( n! ) / (( n-i )! * i!) var nfact = fact(N); var ifact = fact(i); var dfact = fact(N - i); // Using Euler's theorem of Modular // multiplicative inverse to find // the inverse of a number. // (1/a)%mod=a^(m?2)%mod var inv_ifact = binExp(ifact, mod - 2); var inv_dfact = binExp(dfact, mod - 2); var denm = (((inv_ifact % mod) * (inv_dfact % mod)) % mod); var answer = (((nfact % mod) * (denm % mod)) % mod); return answer; } // Function to find the count of // possible strings function countSubstring(N , s , k) { // Number of ways to form all // possible strings var allWays = binExp(26, N); // Number of ways to form strings // that don't contain the input // string as a subsequence var noWays = 0; // Checking for all prefix length // from 0 to |S|-1. for (var i = 0; i < s; ++i) { // To calculate nCi var nCi = calculate_nCi(N, i); // Select the remaining characters // 25 ^ (N-i) var remaining = binExp(25, N - i); var multiply = (((nCi % mod) * (remaining % mod)) % mod); // Add the answer for this prefix // length to the final answer noWays = (((noWays % mod) + (multiply % mod)) % mod); } // Answer is the difference of // allWays and noWays var answer = (((allWays % mod) - (noWays % mod)) % mod); if (answer < 0) answer += mod; // Print the answer document.write(answer); } // Driver code var str = "abc"; var k = 2; var s = str.length; var N = s + k; countSubstring(N, s, k);// This code contributed by umadevi9616</script> |
Output:
6376
Time Complexity: O(N), where N is the length of the given string.
Auxiliary Space: O(1)
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
