Блог пользователя go_anjji_go

Maximal String
Автор go_anjji_go, история, 4 года назад, По-английски

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
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится 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.

→ Ответить
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Shouldn't greedy work?

→ Ответить
»
4 года назад, # |
← 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.

→ Ответить
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 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.

    → Ответить
»
4 года назад, # |
← 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).

→ Ответить