Counting K-Length Strings with Fixed Character in a Unique String
Given a string S of length n containing distinct characters and a character C , the task is to count k-length strings that can be formed using characters from the string S, ensuring each string includes the specified character C, and no characters from the given string S are used more than once. Return the answer by taking modulo of 1e9 + 7.
Example:
Input: C = ‘a’, S = “abc”, k = 2
Output: 4
Explanation: All two-length strings are: {ab, ac, ba, bc, ca, cb}
All valid strings including character ‘C’ are: {ab, ac, ba, ca}Input: C = ‘c’, S = “abcde”, k = 3
Output: 36
Approach:
Think about complement approach that is: Count of total two length strings – Count of two length string that doesn’t containing given character C.
Formula: nCk * k! – (n – 1)Ck * k!
- nCk * k!: Select k elements from n characters (i.e, nCk) and permulte them (i.e, k!)
- (n – 1)Ck * k!: Assume given character is not present in S then selecting k elements from (n – 1) (i.e, (n-1)Ck ) and permute them (k!)
Steps-by-step approach:
- Initialize an array fact to store factorials.
- Calculate factorials up to M using a loop.
- Calculate a^b under modulus mod using binary exponentiation.
- Calculate the modular multiplicative inverse of a under modulus mod.
- Calculate “n choose r” (combination) under modulus mod.
- Calculate the count of k-length strings containing character C from the given string S using above formula.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h> using namespace std; int const M = 1e6 + 10; // Define the maximum size of the array long long const mod = 1e9 + 7; // Define the modulus for calculations vector< long long > fact(M); // Initialize the factorial array // Function to pre-calculate the factorial of numbers up to // M void preCalculateFact() { fact[0] = 1; // 0! = 1 fact[1] = 1; // 1! = 1 // Calculate the factorial for the rest of the numbers for ( int i = 2; i < M; i++) { fact[i] = (fact[i - 1] * i) % mod; } } // Function to calculate a^b under modulus mod using binary // exponentiation long long binaryExpo( long long a, long long b, long long mod) { long long ans = 1; while (b) { if (b & 1) { ans = (ans * a) % mod; } a = (a * a) % mod; b >>= 1; } return ans; } // Function to calculate the modular multiplicative inverse // of a under modulus mod long long modMultiInv( long long a, long long mod) { return binaryExpo(a, mod - 2, mod); } // Function to calculate n choose r under modulus mod int nCr( int n, int k) { return (fact[n] * modMultiInv(fact[k], mod) % mod * modMultiInv(fact[n - k], mod) % mod) % mod; } // Function to solve the problem int solve( int n, int k, char c, string& s) { preCalculateFact(); // Pre-calculate the factorials return (nCr(n, k) * 1LL * fact[k]) - (nCr(n - 1, k) * 1LL * fact[k]); } // Main function int main() { int n = 3; // Size of the string int k = 2; // Length of the strings to be formed char c = 'a' ; // Character that must be included in the // strings string s = "abc"; // Given string cout << solve(n, k, c, s); // Print the solution return 0; } |
Java
import java.util.*; public class Main { static final int M = ( int )1e6 + 10 ; // Define the maximum size of the array static final long mod = ( long )1e9 + 7 ; // Define the modulus for calculations static long [] fact = new long [M]; // Initialize the factorial array // Function to pre-calculate the factorial of numbers up to M static void preCalculateFact() { fact[ 0 ] = 1 ; // 0! = 1 fact[ 1 ] = 1 ; // 1! = 1 // Calculate the factorial for the rest of the numbers for ( int i = 2 ; i < M; i++) { fact[i] = (fact[i - 1 ] * i) % mod; } } // Function to calculate a^b under modulus mod using binary exponentiation static long binaryExpo( long a, long b, long mod) { long ans = 1 ; while (b > 0 ) { if ((b & 1 ) == 1 ) { ans = (ans * a) % mod; } a = (a * a) % mod; b >>= 1 ; } return ans; } // Function to calculate the modular multiplicative inverse of a under modulus mod static long modMultiInv( long a, long mod) { return binaryExpo(a, mod - 2 , mod); } // Function to calculate n choose r under modulus mod static int nCr( int n, int k) { return ( int )(((fact[n] * modMultiInv(fact[k], mod) % mod) * modMultiInv(fact[n - k], mod)) % mod); } // Function to solve the problem static int solve( int n, int k, char c, String s) { preCalculateFact(); // Pre-calculate the factorials return ( int )((nCr(n, k) * 1L * fact[k]) - (nCr(n - 1 , k) * 1L * fact[k])); } // Main function public static void main(String[] args) { int n = 3 ; // Size of the string int k = 2 ; // Length of the strings to be formed char c = 'a' ; // Character that must be included in the strings String s = "abc" ; // Given string System.out.println(solve(n, k, c, s)); // Print the solution } } |
C#
using System; class Program { const int M = 1000000 + 10; // Define the maximum size of the array const long Mod = 1000000007; // Define the modulus for calculations static long [] fact = new long [M]; // Initialize the factorial array // Function to pre-calculate the factorial of numbers up to M static void PreCalculateFact() { fact[0] = 1; // 0! = 1 fact[1] = 1; // 1! = 1 // Calculate the factorial for the rest of the numbers for ( int i = 2; i < M; i++) { fact[i] = (fact[i - 1] * i) % Mod; } } // Function to calculate a^b under modulus mod using binary exponentiation static long BinaryExpo( long a, long b, long mod) { long ans = 1; while (b > 0) { if (b % 2 == 1) { ans = (ans * a) % mod; } a = (a * a) % mod; b >>= 1; } return ans; } // Function to calculate the modular multiplicative inverse of a under modulus mod static long ModMultiInv( long a, long mod) { return BinaryExpo(a, mod - 2, mod); } // Function to calculate n choose r under modulus mod static int nCr( int n, int k) { return ( int )((fact[n] * ModMultiInv(fact[k], Mod) % Mod * ModMultiInv(fact[n - k], Mod) % Mod) % Mod); } // Function to solve the problem static int Solve( int n, int k, char c, string s) { PreCalculateFact(); // Pre-calculate the factorials return ( int )((nCr(n, k) * 1L * fact[k]) - (nCr(n - 1, k) * 1L * fact[k])); } // Main function static void Main( string [] args) { int n = 3; // Size of the string int k = 2; // Length of the strings to be formed char c = 'a' ; // Character that must be included in the strings string s = "abc" ; // Given string Console.WriteLine(Solve(n, k, c, s)); // Print the solution } } |
Javascript
const mod = BigInt(1e9 + 7); // Define the modulus for calculations const M = 1e6 + 10; // Define the maximum size of the array const fact = new Array(M); // Initialize the factorial array // Function to pre-calculate the factorial of numbers up to M function preCalculateFact() { fact[0] = BigInt(1); // 0! = 1 fact[1] = BigInt(1); // 1! = 1 // Calculate the factorial for the rest of the numbers for (let i = 2; i < M; i++) { fact[i] = (fact[i - 1] * BigInt(i)) % mod; } } // Function to calculate a^b under modulus mod using binary exponentiation function binaryExpo(a, b) { let ans = BigInt(1); while (b > BigInt(0)) { if (b & BigInt(1)) { ans = (ans * a) % mod; } a = (a * a) % mod; b >>= BigInt(1); } return ans; } // Function to calculate the modular multiplicative inverse of a under modulus mod function modMultiInv(a) { return binaryExpo(a, mod - BigInt(2)); } // Function to calculate n choose r under modulus mod function nCr(n, k) { return ( (fact[n] * modMultiInv(fact[k]) % mod) * modMultiInv(fact[n - k]) % mod ) % mod; } // Function to solve the problem function solve(n, k, c, s) { preCalculateFact(); // Pre-calculate the factorials return ( (nCr(n, k) * fact[k]) % mod - (nCr(n - 1, k) * fact[k]) % mod ) % mod; } const n = 3; // Size of the string const k = 2; // Length of the strings to be formed const c = 'a' ; // Character that must be included in the strings const s = "abc" ; // Given string console.log(solve(n, k, c, s).toString()); // Print the solution |
Python3
mod = int ( 1e9 + 7 ) # Define the modulus for calculations M = int ( 1e6 + 10 ) # Define the maximum size of the array fact = [ 0 ] * M # Initialize the factorial array # Function to pre-calculate the factorial of numbers up to M def pre_calculate_fact(): fact[ 0 ] = 1 # 0! = 1 fact[ 1 ] = 1 # 1! = 1 # Calculate the factorial for the rest of the numbers for i in range ( 2 , M): fact[i] = (fact[i - 1 ] * i) % mod # Function to calculate a^b under modulus mod using binary exponentiation def binary_expo(a, b, mod): ans = 1 while b: if b & 1 : ans = (ans * a) % mod a = (a * a) % mod b >> = 1 return ans # Function to calculate the modular multiplicative inverse of a under modulus mod def mod_multi_inv(a, mod): return binary_expo(a, mod - 2 , mod) # Function to calculate n choose r under modulus mod def nCr(n, k): return (fact[n] * mod_multi_inv(fact[k], mod) % mod * mod_multi_inv(fact[n - k], mod) % mod) % mod # Function to solve the problem def solve(n, k, c, s): pre_calculate_fact() # Pre-calculate the factorials return (nCr(n, k) * fact[k] - nCr(n - 1 , k) * fact[k]) # Main function def main(): n = 3 # Size of the string k = 2 # Length of the strings to be formed c = 'a' # Character that must be included in the strings s = "abc" # Given string print (solve(n, k, c, s)) # Print the solution if __name__ = = "__main__" : main() |
4
Time Complexity: O(M), where M is size for storing factorial
Auxiliary Space: O(M)
Related Article: Counting k-Length Strings with Character C Allowing Repeated Characters (SET-2)
Contact Us