We are provided with a string A (may contain repeated characters as well ). One needs to make all possible permutations of A , and find out how many pairs of strings chosen from these permutations are not similar.
Two strings are similar if we can make both of them exactly same by carrying out at most 1 swap in each of them .
Example :- if we are provided with string abcd , then for permutation abcd , the permutations which are not similar to it are bcda , bdac , cadb , cdba , dabc , dcab . Similar is the case for other permuations as well. So overall number of desired pairs are 24*6=144 .
I tried solving it for each possible pair by approach mentioned here https://stackoverflow.com/questions/18292202/finding-the-minimum-number-of-swaps-to-convert-one-string-to-another-where-the
But as the permutations can be large enough , I need a better approach of solving this.