go_anjji_go's blog

Maximal String
By go_anjji_go, history, 4 years ago, In English

You are given a string. You can perform at most K operations on this string. In each operation, you take two different indices i and j and swap the characters at these positions. What is the maximal lexicographical string that you can obtain. This question can be solved using backtracking but I was looking for some other efficient approach, maybe greedy or DP. Kindly share your views.

  • Vote: I like it
  • +8
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I too tried for DP or greedy approach but can't find any. We can solve using greedy approach only when character in given string are pairwise distinct. You can refer IBit backtracking and greedy for more.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Shouldn't greedy work?

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +13 Vote: I do not like it

The problem of finding minimum number of swaps to sort an arbitrary array can be reduced in polynomial time to your problem. Given that the first problem is NP-complete (for example, check out this discussion), your problem can't be solved in polynomial time, unless P = NP.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The problem you mentioned isn't exactly reducible to this problem, because the alphabet size here is constant (atleast independent of the size of array). There might exist a $$$O(2^{alpha})$$$ algorithm for this problem (where $$$alpha$$$ is the size of alphabets, 26 if the string contains only lower case letters), and it still will be considered solvable in polynomial time.

    → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

I think it can be solved in $$$O(n log n)$$$. For every $$$i$$$ ($$$1<=i<=n$$$) we calculate $$$pos$$$, where $$$s[pos]=max(s[i],....,s[n])$$$ and $$$s[pos]>max(s[pos+1],....,s[n])$$$ ($$$pos$$$ is the right most position of the largest value from the remaining interval). If $$$s[pos]==s[i]$$$ then we do nothing. Else, we swap the values at $$$s[i]$$$ and $$$s[pos]$$$, and increment the number of swaps. The algorithm stops when we have reached k swaps or $$$i==n$$$. $$$pos$$$ can be found using a segment tree ($$$O (log n)$$$). The idea is that, at each step, we have to select the largest possible character from the remaining string (to ensure that the string we have built is maximal). We also pick the right most position to ensure that the remaining string is maximal (in case we end the algorithm at the next step).

→ Reply