Here is a good explanation of a next lexicographical permutation algorithm:

http://www.nayuki.io/page/next-lexicographical-permutation-algorithm

All of this C++ next_permutation() guys are a bunch of sissies.

For all those who are still trying to figure out why are they failing 1,2 and 3 testcase even when they are getting correct output for most, check for the following string.

---->Input: zzzayybbaa

---->correct output : zzzbaaabyy

---->incorrect output : zzzaaabbyy (what I was getting)

took me quite a while to figure it out.

Having 100,000 tests in a testcase is exessive and makes debugging a pain. 1000 would have been enough to catch the badly performing implementations.

For all those people whose code is getting failed for testcases#2 & 3, check if your code handles the condition when the length of input string is 1 i.e. single letter strings in which case the correct output would be "no answer"... that was the problem with my code. hope it helps :)