gauravit's blog

By gauravit, history, 2 weeks ago, In English

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?

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
2 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

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)

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Oh sorry, two loops are needed anyway — to count the symbols and to sum the unnecessary pairs. But this is O(N), not O(N^2)

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think still need to sum up one for each parcel (a[i] * (a[i] — 1) / 2) because you need to consider at least one representation for repeated letters. For example, in "geek" you have ge¹e²k and ge²e¹k. In your count you are desconsidering both.

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Let's say we have to print the result also. Then What would be the optimized approach?

      • »
        »
        »
        »
        2 weeks ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        Suppose there are m non-repeated letters in the original string of size n. Save the positions of the non-repeated letters in an array and the position of the repeated letters in another array. Then you can generate all possible swaps in O(n*m). Notice that m is bounded by the size of the alphabet. So in practice, it will work in O(n).

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

we can do it in O(n). check this.

  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you please suggest that how to print this also?

    • »
      »
      »
      10 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      If you want to print all the strings it'll take O(n^2).

      • »
        »
        »
        »
        10 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        It means we have to run loop twice with hashset. There is no any other way. I was thinking if some other technique could help.

        But no issue :P. Thank you Pallove