Bigger is Greater
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 .
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
php
<?php
// Complete the biggerIsGreater function below.
function getmin($ar, $e) {
$min = max($ar);
foreach($ar as $r) {
if($r <= $min && $r > $e) {
$min = $r;
}
}
return $min;
}
function swap($ar, $e) {
$min = getmin($ar, $e);
//echo $min;
if($min > $e) {
for($i = 0; $i < count($ar); $i++) {
if($ar[$i] == $min) {
$ar[$i] = $e;
break;
}
}
rsort($ar);
$ar[] = $min;
} else {
sort($ar);
$ar[] = $e;
}
$ar = array_reverse($ar);
return $ar;
}
function biggerIsGreater($w) {
$arr = [];
for($i = 0; $i < strlen($w); $i++) {
$arr[] = ord($w[$i]);
}
$ar = [];
$n = count($arr);
$tps = [];
$idx = 0;
for($i = 0; $i < strlen($w); $i++) {
//$ar[] = $arr[$n - 1 - $i];
//$tps = $ar;
$tps = array_reverse($tps);
$tps[] = $arr[$n - 1 - $i];
$tps = array_reverse($tps);
//$tmp = $ar;
$ar = swap($ar, $arr[$n - 1 - $i]);
$idx = $i;
//print_r($ar);
//print_r($tps);
if($ar != $tps)
break;
}
if($ar != $tps) {
$arj = [];
for($j = 0; $j < $n - 1 - $idx; $j++) {
$arj[] = $arr[$j];
}
foreach($ar as $te) {
$arj[] = $te;
}
$s = "";
foreach($arj as $tf) {
$s .= chr($tf);
}
return $s;
}
return 'no answer';
}
$fptr = fopen(getenv("OUTPUT_PATH"), "w");
$stdin = fopen("php://stdin", "r");
fscanf($stdin, "%d\n", $T);
for ($T_itr = 0; $T_itr < $T; $T_itr++) {
$w = '';
fscanf($stdin, "%[^\n]", $w);
$result = biggerIsGreater($w);
fwrite($fptr, $result . "\n");
}
fclose($stdin);
fclose($fptr);
Comments
Post a Comment