Counting k-Length Strings with Character C Allowing Repeated Characters
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 characters from the given string S are used multiple times. Return the answer by taking the modulo of 1e9 + 7.
Note: There must be occurrence of given character in given string S.
Example:
Input: C = ‘a’, S = “abc”, k = 2
Output: 5
Explanation: All two-length strings are: {ab, ac, ba, bc, ca, cb, aa, bb, cc}
All valid strings including character ‘C’ are: {ab, ac, ba, ca, aa}Input: C = ‘d’, S = “abcd”, k = 3
Output: 61
Approach:
Think about complement approach that is: Count of total k length strings – Count of k length strings that doesn’t containing given character C.
Formula: nk – (n – 1)k
- nk: At every place of k length string have n option to fill the characters. So, k length string will have total nk options.
- (n – 1)k: We have assumed there doesn’t exist any occurrence of given character ‘C‘. So, there would be only (n – 1) characters left and at every place of k length string have (n-1) options to fill the characters. So, k length string will have total (n – 1)k options
Steps-by-step approach:
- Define constant M as 1e6 + 10 for the maximum size of the array.
- Define constant mod as 1e9 + 7 for the modulus in calculations.
- Binary Exponentiation Function (binaryExpo) for calculating power a^b:
- Implement a function to calculate a^b under modulus mod using binary exponentiation.
- Initialize a variable ans to 1.
- Iterate through the binary representation of b.
- If the current bit is 1, update ans with (ans * a) % mod.
- Update a with (a * a) % mod and right-shift b.
- Return the final value of ans.
- Problem-solving Function (solve):
- Implement a function to solve the problem.
- Calculate binaryExpo(n, k) and binaryExpo(n – 1, k).
- Return the difference between the two results.
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 // Function to calculate a^b under modulus mod using binary // exponentiation long long binaryExpo( long long a, long long b) { long long ans = 1; while (b) { if (b & 1) { ans = (ans * a) % mod; } a = (a * a) % mod; b >>= 1; } return ans; } // Function to solve the problem int solve( int n, int k, char c, string& s) { return binaryExpo(n, k) - binaryExpo(n - 1, k); } // Main function int main() { int n = 3; // Size of the string int k = 2; // Length of the strings to be formed char c = 'b' ; // 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 = 1000010 ; // Define the maximum size of the array static final long mod = 1000000007 ; // Define the modulus for calculations // Function to calculate a^b under modulus mod using binary exponentiation static long binaryExpo( long a, long b) { long ans = 1 ; while (b > 0 ) { if ((b & 1 ) == 1 ) { ans = (ans * a) % mod; } a = (a * a) % mod; b >>= 1 ; } return ans; } // Function to solve the problem static int solve( int n, int k, char c, String s) { return ( int ) ((binaryExpo(n, k) - binaryExpo(n - 1 , k) + mod) % mod); } // 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 = 'b' ; // Character that must be included in the strings String s = "abc" ; // Given string System.out.println(solve(n, k, c, s)); // Print the solution } } |
Python
# Define the maximum size of the array M = 10 * * 6 + 10 # Define the modulus for calculations mod = 10 * * 9 + 7 # Function to calculate a^b under modulus mod using binary exponentiation def binaryExpo(a, b): ans = 1 while b: if b & 1 : ans = (ans * a) % mod a = (a * a) % mod b >> = 1 return ans # Function to solve the problem def solve(n, k, c, s): return binaryExpo(n, k) - binaryExpo(n - 1 , k) # Main function def main(): n = 3 # Size of the string k = 2 # Length of the strings to be formed c = 'b' # Character that must be included in the strings s = "abc" # Given string print (solve(n, k, c, s)) # Print the solution # Call the main function main() |
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 // Function to calculate a^b under modulus mod using // binary exponentiation static long BinaryExpo( long a, long b) { long ans = 1; while (b > 0) { if ((b & 1) == 1) { ans = (ans * a) % Mod; } a = (a * a) % Mod; b >>= 1; } return ans; } // Function to solve the problem static int Solve( int n, int k, char c, string s) { return ( int )(BinaryExpo(n, k) - BinaryExpo(n - 1, 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 = 'b' ; // Character that must be included in // the strings string s = "abc" ; // Given string Console.WriteLine( Solve(n, k, c, s)); // Print the solution } } // This code calculates the difference between two values // raised to the power of k under modulus Mod. |
Javascript
const M = 10**6 + 10; // Define the maximum size of the array const mod = 10**9 + 7; // Define the modulus for calculations // Function to calculate a^b under modulus mod using binary exponentiation function binaryExpo(a, b) { let ans = 1; while (b) { if (b & 1) { ans = (ans * a) % mod; } a = (a * a) % mod; b >>= 1; } return ans; } // Function to solve the problem function solve(n, k, c, s) { return binaryExpo(n, k) - binaryExpo(n - 1, k); } const n = 3; // Size of the string const k = 2; // Length of the strings to be formed const c = 'b' ; // Character that must be included in the strings const s = "abc" ; // Given string console.log(solve(n, k, c, s)); // Print the solution |
5
Time Complexity: O(log(k))
Auxiliary Space: O(1)
Related Article: Counting K-Length Strings with Fixed Character in a Unique String (SET-1)
Contact Us