Given a string ‘s’ and a character ‘c’, the task is to find the number of permutations of the string in which all the occurrences of the character ‘c’ will be together (one after another).
Examples :
Input: Str = “AKA” ch = ‘A’
Output: 2
Explanation: All the unique permutations of AKA are : AKA, AAK and KAA
‘A’ comes consecutively only twice. Hence, the answer is 2Input: str= “MISSISSIPPI” ch = ‘S’
Output: 840
Naive Approach:
- Generate all the permutations of the given string.
- For each permutation check whether all occurrences of the character appear together.
- The count of the permutations from the previous step is the answer.
Efficient Approach: Let the length of the string be ‘l’ and the frequency of the character in the string be ‘n’.
- Store the frequency of every character of the string.
- If the character is not present in the string then the output will be ‘0’.
- Consider all the occurrences of the character as a combined single character.
- So, ‘l’ will become ‘l – occ + 1’ where ‘occ’ is the total occurrence of the given character and ‘l’ is the new length of the string.
- Return ( (Factorial of l) / (Product of the factorials of the no. of occurrences of each character except the given character) )
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to return factorial// of the number passed as argumentlong long int fact(int n){ long long result = 1; for (int i = 1; i <= n; i++) result *= i; return result;}// Function to get the total permutations// which satisfy the given conditionint getResult(string str, char ch){ // Create has to store count // of each character int has[26] = { 0 }; // Store character occurrences for (int i = 0; i < str.length(); i++) has[str[i] - 'A']++; // Count number of times // Particular character comes int particular = has[ch - 'A']; // If particular character isn't // present in the string then return 0 if (particular == 0) return 0; // Remove count of particular character has[ch - 'A'] = 0; // Total length // of the string int total = str.length(); // Assume all occurrences of // particular character as a // single character. total = total - particular + 1; // Compute factorial of the length long long int result = fact(total); // Divide by the factorials of // the no. of occurrences of all // the characters. for (int i = 0; i < 26; i++) { if (has[i] > 1) { result = result / fact(has[i]); } } // return the result return result;}// Driver Codeint main(){ string str = "MISSISSIPPI"; // Assuming the string and the character // are all in uppercase cout << getResult(str, 'S') << endl; return 0;} |
Java
// Java implementation of above approachimport java.util.*;class solution{// Function to return factorial// of the number passed as argument static int fact(int n){ int result = 1; for (int i = 1; i <= n; i++) result *= i; return result;}// Function to get the total permutations// which satisfy the given conditionstatic int getResult(String str, char ch){ // Create has to store count // of each character int has[] = new int[26]; for(int i=0;i<26;i++) has[i]=0; // Store character occurrences for (int i = 0; i < str.length(); i++) has[str.charAt(i) - 'A']++; // Count number of times // Particular character comes int particular = has[ch - 'A']; // If particular character isn't // present in the string then return 0 if (particular == 0) return 0; // Remove count of particular character has[ch - 'A'] = 0; // Total length // of the string int total = str.length(); // Assume all occurrences of // particular character as a // single character. total = total - particular + 1; // Compute factorial of the length int result = fact(total); // Divide by the factorials of // the no. of occurrences of all // the characters. for (int i = 0; i < 26; i++) { if (has[i] > 1) { result = result / fact(has[i]); } } // return the result return result;}// Driver Codepublic static void main(String args[]){ String str = "MISSISSIPPI"; // Assuming the string and the character // are all in uppercase System.out.println( getResult(str, 'S') );}}//contributed by Arnab Kundu |
Python 3
# Python3 implementation of # the approach # Function to return factorial # of the number passed as argument def fact(n) : result = 1 for i in range(1, n + 1) : result *= i return result# Function to get the total permutations # which satisfy the given condition def getResult(string, ch): # Create has to store count # of each character has = [0] * 26 # Store character occurrences for i in range(len(string)) : has[ord(string[i]) - ord('A')] += 1 # Count number of times # Particular character comes particular = has[ord(ch) - ord('A')] # If particular character isn't # present in the string then return 0 if particular == 0 : return 0 # Remove count of particular character has[ord(ch) - ord('A')] = 0 # Total length # of the string total = len(string) # Assume all occurrences of # particular character as a # single character. total = total - particular + 1 # Compute factorial of the length result = fact(total) # Divide by the factorials of # the no. of occurrences of all # the characters. for i in range(26) : if has[i] > 1 : result /= fact(has[i]) # return the result return result# Driver codeif __name__ == "__main__" : string = "MISSISSIPPI" # Assuming the string and the character # are all in uppercase print(getResult(string,'S'))# This code is contributed # by ANKITRAI1 |
C#
// C# implementation of above approachusing System;class GFG{// Function to return factorial// of the number passed as argumentstatic int fact(int n){ int result = 1; for (int i = 1; i <= n; i++) result *= i; return result;}// Function to get the total permutations// which satisfy the given conditionstatic int getResult(string str, char ch){ // Create has to store count // of each character int []has = new int[26]; for(int i = 0; i < 26; i++) has[i] = 0; // Store character occurrences for (int i = 0; i < str.Length; i++) has[str[i] - 'A']++; // Count number of times // Particular character comes int particular = has[ch - 'A']; // If particular character // isn't present in the string // then return 0 if (particular == 0) return 0; // Remove count of particular character has[ch - 'A'] = 0; // Total length of the string int total = str.Length; // Assume all occurrences of // particular character as a // single character. total = total - particular + 1; // Compute factorial of the length int result = fact(total); // Divide by the factorials of // the no. of occurrences of all // the characters. for (int i = 0; i < 26; i++) { if (has[i] > 1) { result = result / fact(has[i]); } } // return the result return result;}// Driver Codepublic static void Main(){ string str = "MISSISSIPPI"; // Assuming the string and the // character are all in uppercase Console.WriteLine(getResult(str, 'S') );}}// This code is contributed by anuj_67 |
PHP
<?php // PHP implementation of the approach// Function to return factorial of// the number passed as argumentfunction fact($n){ $result = 1; for ($i = 1; $i <= $n; $i++) $result *= $i; return $result;}// Function to get the total permutations// which satisfy the given conditionfunction getResult($str, $ch){ // Create has to store count // of each character $has = array_fill(0, 26, NULL); // Store character occurrences for ($i = 0; $i < strlen($str); $i++) $has[ord($str[$i]) - ord('A')]++; // Count number of times // Particular character comes $particular = $has[ord($ch) - ord('A')]; // If particular character isn't // present in the string then return 0 if ($particular == 0) return 0; // Remove count of particular character $has[ord($ch) - ord('A')] = 0; // Total length // of the string $total = strlen($str); // Assume all occurrences of // particular character as a // single character. $total = $total - $particular + 1; // Compute factorial of the length $result = fact($total); // Divide by the factorials of // the no. of occurrences of all // the characters. for ($i = 0; $i < 26; $i++) { if ($has[$i] > 1) { $result = $result / fact($has[$i]); } } // return the result return $result;}// Driver Code$str = "MISSISSIPPI";// Assuming the string and the character// are all in uppercaseecho getResult($str, 'S')."\n" ;// This code is contributed by ita_c?> |
Javascript
<script> // Javascript implementation of the approach// Function to return factorial of// the number passed as argumentfunction fact(n){ let result = 1; for (let i = 1; i <= n; i++) result *= i; return result;}// Function to get the total permutations// which satisfy the given conditionfunction getResult(str, ch){ // Create has to store count // of each character let has = new Array(26).fill(null); // Store character occurrences for (let i = 0; i < str.length; i++) has[str.charCodeAt(i) - 'A'.charCodeAt(0)]++; // Count number of times // Particular character comes particular = has[ch.charCodeAt(0) - 'A'.charCodeAt(0)]; // If particular character isn't // present in the string then return 0 if (particular == 0) return 0; // Remove count of particular character has[ch.charCodeAt(0) - 'A'.charCodeAt(0)] = 0; // Total length // of the string let total = str.length; // Assume all occurrences of // particular character as a // single character. total = total - particular + 1; // Compute factorial of the length let result = fact(total); // Divide by the factorials of // the no. of occurrences of all // the characters. for (let i = 0; i < 26; i++) { if (has[i] > 1) { result = result / fact(has[i]); } } // return the result return result;}// Driver Codelet str = "MISSISSIPPI";// Assuming the string and the character// are all in uppercasedocument.write(getResult(str, 'S') + "<br>");// This code is contributed by gfgking</script> |
Output
840
Complexity Analysis:
- Time Complexity: O(n) where n is the size of the string.
- Auxiliary Space: O(1) as constant space is taken.
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!
