Given a string S containing lowercase English alphabet characters. The task is to calculate the number of distinct strings that can be obtained after performing exactly one swap.
In one swap, Geek can pick two distinct indexes i and j (i.e 1 < i < j < |S| ) of the string, then swap the characters at the position i and j.
S = "geek" Output: 6 Explanation: After one swap, there are only 6 distinct strings possible. (i.e "egek","eegk","geek","geke","gkee" and "keeg")`
I have made the solution using 2 for loops and a HashSet. I am thinking that is there any more optimized way to solve this problem?
I guess you don't need any loops here. Lets imagine all the symbols in the word are different, then answer is (n * (n — 1) / 2) where n is the word length (count of choosing two different indexes). Now lets consider any words. Then we need to substract all the pairs with equal symbols. Let count a[i] = count of symbols i in the word. Then answer is (n * (n — 1) / 2) — SUM_FOR_EACH_I(a[i] * (a[i] — 1) / 2)
we can do it in O(n). check this.
Can you please suggest that how to print this also?
If you want to print all the strings it'll take O(n^2).