forked from algorhythms/HackerRankAlgorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Bigger is Greater.py
59 lines (47 loc) · 1.39 KB
/
Bigger is Greater.py
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
# -*- coding: utf-8 -*-
"""
Problem Statement
Given a word w, rearrange the letters of w to construct another word s in such a way that, s is lexicographically
greater than w. In case of multiple possible answers, find the lexicographically smallest one.
Input Format
The first line of input contains t, number of test cases. Each of the next t lines contains w.
"""
__author__ = 'Danyang'
class Solution(object):
def solve(self, cipher):
"""
similar to next permutation
:param cipher: the cipher
"""
A = list(cipher)
A = map(ord, A)
n = len(A)
a = -1
for i in xrange(n - 1, 0, -1):
if A[i - 1] < A[i]:
a = i - 1
break
else:
return "no answer"
b = -1
for i in xrange(n - 1, a, -1):
if A[i] > A[a]:
b = i
break
else:
return "no answer"
A[a], A[b] = A[b], A[a] # swap
A = A[:a + 1] + A[n - 1:a:-1] # reverse
return "".join(map(chr, A))
if __name__ == "__main__":
import sys
f = open("1.in", "r")
# f = sys.stdin
solution = Solution()
testcases = int(f.readline().strip())
for t in xrange(testcases):
# construct cipher
cipher = f.readline().strip()
# solve
s = "%s\n" % (solution.solve(cipher))
print s,