Hackerrank - Bigger is Greater Solution
Lexicographical order is often known as alphabetical order when dealing with strings. A string is greater than another string if it comes later in a lexicographically sorted list.
Given a word, create a new word by swapping some or all of its characters. This new word must meet two criteria:
- It must be greater than the original word
- It must be the smallest word that meets the first condition
For example, given the word , the next largest word is .
Complete the function biggerIsGreater below to create and return the new string meeting the criteria. If it is not possible, return no answer
.
Function Description
Complete the biggerIsGreater function in the editor below. It should return the smallest lexicographically higher string possible from the given string or no answer
.
biggerIsGreater has the following parameter(s):
- w: a string
Input Format
The first line of input contains , the number of test cases.
Each of the next lines contains .
Constraints
- will contain only letters in the range ascii[a..z].
Output Format
For each test case, output the string meeting the criteria. If no answer exists, print no answer
.
Sample Input 0
5
ab
bb
hefg
dhck
dkhc
Sample Output 0
ba
no answer
hegf
dhkc
hcdk
Explanation 0
- Test case 1:
ba
is the only string which can be made by rearrangingab
. It is greater. - Test case 2:
It is not possible to rearrangebb
and get a greater string. - Test case 3:
hegf
is the next string greater thanhefg
. - Test case 4:
dhkc
is the next string greater thandhck
. - Test case 5:
hcdk
is the next string greater thandkhc
.
Sample Input 1
6
lmno
dcba
dcbb
abdc
abcd
fedcbabcd
Sample Output 1
lmon
no answer
no answer
acbd
abdc
fedcbabdc
Solution in Python
def biggerIsGreater(w):
arr = list(w)
# Find non-increasing suffix
i = len(arr) - 1
while i > 0 and arr[i - 1] >= arr[i]:
i -= 1
if i <= 0:
return "no answer"
# 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 "".join(arr)
for _ in range(int(input())):
print(biggerIsGreater(input()))
Reference resource:
https://www.nayuki.io/page/next-lexicographical-permutation-algorithm