Horje
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

Output

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)


 


Reffered: https://www.geeksforgeeks.org

Combinatorial

Related
Counting K-Length Strings with Fixed Character in a Unique String Counting K-Length Strings with Fixed Character in a Unique String
Count all ordered pairs (A, B) such that intersection of A and B becomes K Count all ordered pairs (A, B) such that intersection of A and B becomes K
Count all ordered pairs (A, B) such that A and B are disjoint Count all ordered pairs (A, B) such that A and B are disjoint
Number of ways to color the balls (Ball Coloring) Number of ways to color the balls (Ball Coloring)
Basics of Combinatorics for Competitive Programming Basics of Combinatorics for Competitive Programming

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 18



 

Horje