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.

Link

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()

About the author

Add comment

Archives

Categories