### go_anjji_go's blog

By go_anjji_go, history, 7 weeks ago,

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.

• +8

 » 7 weeks ago, # |   0 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.
 » 7 weeks ago, # |   0 Shouldn't greedy work?
 » 7 weeks ago, # | ← Rev. 2 →   +13 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.
•  » » 7 weeks ago, # ^ |   0 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.
 » 7 weeks ago, # | ← Rev. 2 →   +5 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).
•  » » 7 weeks ago, # ^ | ← Rev. 2 →   +4 fails when string is "4288" and k=2