• + 0 comments

    Going from right to left, stop as soon as the predecessor character is greater than the current character. Then find the rightmost such such character and swap. Finally, sort the characters to the right of the current character. The effect of this procedure is to find the lowest possible lexicographic position which, when incremented by swapping, will be greater than the original string, and then to minimze all the lower positions. The resulting string is guaranteed to be lexicographically greater than the original, and any swap will be either greater than this string or smaller than the original string.

    def biggerIsGreater(w):
        w = list(w)
        right_end = len(w) - 1
        left, swapped = right_end - 1, False
        while not swapped and left > -1:
            right = left + 1
            if w[left] < w[right]:
                while right <= right_end and w[left] < w[right]:
                    right += 1
                w[left], w[right - 1], swapped = w[right - 1], w[left], True
            left -= 1
        if not swapped:
            return 'no answer'
        return ''.join(w[:left+2] + sorted(w[left+2:]))