Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

user311's blog

By user311, history, 7 weeks ago, In English

I didn't notice that as per the question statement, we can only switch adjacent characters to reach the original string.

If this wasn't the case and we could switch any characters of the string, how would you solve it.

I wrote a greedy solution: complete as many possible cycles of A -> N -> T -> O -> A until we exhaust the least frequent character. Followed by smaller and smaller cycles.

by completing cycles A -> N -> O -> A, I mean swap 'A' and 'N', swap 'N' and 'O' and so on.

code

Code

Link to Problem

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