CSES Solutions – Creating Strings II
Given a string, your task is to calculate the number of different strings that can be created using its characters.
Examples:
Input: S = “aa”
Output: 1
Explanation: There is only 1 possible string: “aa”.Input: S = “aabac”
Output: 20
Explanation: There are 20 possible strings: “aaabc”, “aaacb”, “aabac”, “aabca”, “aacab”, “aacba”, “abaac”, “abaca”, “abcaa”, “acaab”, “acaba”, “acbaa”, “baaac”, “baaca”, “bacaa”, “bcaaa”, “caaab”, “caaba”, “cabaa” and “cbaaa”.
Approach: To solve the problem, follow the below idea:
We can use the concept of permutations to solve this problem. Given a string of the length n the number of the different strings that can be created using its characters is n! where n! represents the factorial of the n.
However, since the characters in the given string might be repeated we need to the consider the repetitions. We’ll calculate the factorial of the length of string and then divide it by the factorial of the count of the each character’s occurrence.
Below is the implementation of the algorithm:
#include <iostream>
#include <vector>
#define MOD 1000000007
using namespace std;
// Function to calculate factorial modulo MOD
long long factorial(int n)
{
long long result = 1;
for (int i = 2; i <= n; ++i) {
result = (result * i) % MOD;
}
return result;
}
// Function to the calculate modular exponentiation
long long mod_exp(long long base, long long exp,
long long mod)
{
long long result = 1;
while (exp > 0) {
if (exp % 2 == 1) {
result = (result * base) % mod;
}
base = (base * base) % mod;
exp /= 2;
}
return result;
}
// Function to the calculate modular inverse using Fermat's
// Little Theorem
long long mod_inverse(long long n, long long mod)
{
return mod_exp(n, mod - 2, mod);
}
int main()
{
string s = "aabac";
// Count occurrences of each character
vector<int> count(26, 0);
for (char c : s) {
count[c - 'a']++;
}
// Calculate the factorial of the length of the string
long long ans = factorial(s.size());
// Divide by the factorial of the counts of each
// character
for (int i = 0; i < 26; ++i) {
if (count[i] > 0) {
ans = (ans
* mod_inverse(factorial(count[i]), MOD))
% MOD;
}
}
cout << ans << endl;
return 0;
}
import java.util.Arrays;
public class Main {
static final long MOD = 1000000007;
// Function to calculate factorial modulo MOD
static long factorial(int n)
{
long result = 1;
for (int i = 2; i <= n; ++i) {
result = (result * i) % MOD;
}
return result;
}
// Function to the calculate modular exponentiation
static long modExp(long base, long exp, long mod)
{
long result = 1;
while (exp > 0) {
if (exp % 2 == 1) {
result = (result * base) % mod;
}
base = (base * base) % mod;
exp /= 2;
}
return result;
}
// Function to the calculate modular inverse using
// Fermat's Little Theorem
static long modInverse(long n, long mod)
{
return modExp(n, mod - 2, mod);
}
public static void main(String[] args)
{
String s = "aabac";
// Count occurrences of each character
int[] count = new int[26];
for (char c : s.toCharArray()) {
count[c - 'a']++;
}
// Calculate the factorial of the length of the
// string
long ans = factorial(s.length());
// Divide by the factorial of the counts of each
// character
for (int i = 0; i < 26; ++i) {
if (count[i] > 0) {
ans = (ans
* modInverse(factorial(count[i]),
MOD))
% MOD;
}
}
System.out.println(ans);
}
}
MOD = 10**9 + 7
# Function to the calculate factorial modulo MOD
def factorial(n):
result = 1
for i in range(2, n + 1):
result = (result * i) % MOD
return result
# Function to calculate modular exponentiation
def mod_exp(base, exp, mod):
result = 1
while exp > 0:
if exp % 2 == 1:
result = (result * base) % mod
base = (base * base) % mod
exp //= 2
return result
# Function to calculate modular inverse using the Fermat's Little Theorem
def mod_inverse(n, mod):
return mod_exp(n, mod - 2, mod)
# Main function
def main():
s = "aabac"
# Count occurrences of the each character
count = [0] * 26
for c in s:
count[ord(c) - ord('a')] += 1
# Calculate the factorial of the length of string
ans = factorial(len(s))
# Divide by the factorial of the counts of the each character
for i in range(26):
if count[i] > 0:
ans = (ans * mod_inverse(factorial(count[i]), MOD)) % MOD
print(ans)
if __name__ == "__main__":
main()
const MOD = BigInt(10**9 + 7);
// Function to calculate the factorial modulo MOD
function factorial(n) {
let result = BigInt(1);
for (let i = BigInt(2); i <= n; i++) {
result = (result * i) % MOD;
}
return result;
}
// Function to calculate modular exponentiation
function modExp(base, exp, mod) {
let result = BigInt(1);
while (exp > 0n) {
if (exp % 2n === 1n) {
result = (result * base) % mod;
}
base = (base * base) % mod;
exp = exp / 2n;
}
return result;
}
// Function to calculate modular inverse using Fermat's Little Theorem
function modInverse(n, mod) {
return modExp(n, mod - BigInt(2), mod);
}
// Main function
function main() {
const s = "aabac";
// Count occurrences of each character
const count = Array(26).fill(BigInt(0));
for (let c of s) {
count[c.charCodeAt(0) - 'a'.charCodeAt(0)]++;
}
// Calculate the factorial of the length of the string
let ans = factorial(BigInt(s.length));
// Divide by the factorial of the counts of each character
for (let i = 0; i < 26; i++) {
if (count[i] > BigInt(0)) {
ans = (ans * modInverse(factorial(count[i]), MOD)) % MOD;
}
}
console.log(ans.toString()); // Convert BigInt to string for output
}
main();
// This code is contributed by Shivam Gupta
Output
20
Time Complexity: O(N logN)
Auxiliary Space: O(N)
Contact Us