# HackerRank ‘Bigger is Greater’ Solution

H
##### Short Problem Definition:

Given a word w, rearrange the letters of w to construct another word in such a way that is lexicographically greater than w. In case of multiple possible answers, find the lexicographically smallest one among them.

Bigger is Greater

##### Complexity:

time complexity is O(N)

space complexity is O(N)

##### Execution:

This task challenges us to find the next permutation of any given array. There are many implementations available online and it is worthwhile comparing them . I would recommend reading the article by Nayuki or re-implementing the std::next_permutation.

##### Solution:
 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 `def` `next_permutation(arr):` `    ``# Find non-increasing suffix` `    ``i ``=` `len``(arr) ``-` `1` `    ``while` `i > ``0` `and` `arr[i ``-` `1``] >``=` `arr[i]:` `        ``i ``-``=` `1` `    ``if` `i <``=` `0``:` `        ``return` `False` `    `  `    ``# Find successor to pivot` `    ``j ``=` `len``(arr) ``-` `1` `    ``while` `arr[j] <``=` `arr[i ``-` `1``]:` `        ``j ``-``=` `1` `    ``arr[i ``-` `1``], arr[j] ``=` `arr[j], arr[i ``-` `1``]` `    `  `    ``# Reverse suffix` `    ``arr[i : ] ``=` `arr[``len``(arr) ``-` `1` `: i ``-` `1` `: ``-``1``]` `    ``return` `True` `        `  `def` `main():` `    ``t ``=` `input``()` `    ``for` `_ ``in` `xrange``(t):` `        ``s ``=` `list``(``raw_input``())` `        ``if` `next_permutation(s):` `            ``print` `"".join(s)` `        ``else``:` `            ``print` `"no answer"` `    `  `if` `__name__ ``=``=` `'__main__'``:` `    ``main()` 