- Combinatorial, Greedy, permutation, Strings

Count of distinct permutation of a String obtained by swapping only unequal characters

Given a string find the number of unique permutations that can be obtained by swapping two indices such that the elements at these indices are distinct.NOTE: Swapping is always performed in the original string.Examples:Input: str = “sstt”Output: 5Explaination: Swap str[0] with str[2], string obtained “tsst” which is valid (str[0]!=str[2])Swap str[0] with str[3]. string obtained “tsts”Swap str[1] with str[2], string obtained “stst”Swap str[1] with str[3], string obtained “stts”Hence total 5 strings can be obtained including the given string (“sstt”)Input: str = “abcd”Output: 7Approach: The problem can be solved using HashMap by the following steps:Create a hashmap and store the frequency of every character of the given string.Create a variable count, to store the total number of characters in the given string, i.e. count=str.length() and a variable ans to store the number of unique permutations possible and initialize ans=0.Traverse the string and for each character: Find the number of different characters present in the right of the current index. This can be done by subtracting the frequency of that character by the total count.Now add this calculated value to ans, as this is the number of characters with which the current character can be swapped to create a unique permutation. Now, Reduce the frequency of the current character and count by 1, so that it cannot interfere with the calculations of the same elements present to the right of it. Return ans+1, because the given string is also a unique permutation.C++#include using namespace std;  int validPermutations(string str){    unordered_map m;                      int count = str.length(), ans = 0;              for (int i = 0; i < str.length(); i++) {        m[str[i]]++;    }    for (int i = 0; i < str.length(); i++) {                        ans += count - m[str[i]];                                          m[str[i]]--;        count--;    }              return ans + 1;}  int main(){    string str = "sstt";    cout