Hackerrank Bigger is Greater Solution
.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0}
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.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0}
The first line of input contains , the number of test cases.
Each of the next lines contains .
Constraints.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0}
- will contain only letters in the range ascii[a..z].
Output Format.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0}
For each test case, output the string meeting the criteria. If no answer exists, print no answer
.
Sample Input 0.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0} 5abbbhefgdhckdkhc
Sample Output 0.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0} bano answerhegfdhkchcdk
Explanation 0.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 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.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0} 6lmnodcbadcbbabdcabcdfedcbabcd
Sample Output 1.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0} lmonno answerno answeracbdabdcfedcbabdc
Solution in java8
Approach 1.
import java.io.*;
import java.util.*;
public class Solution {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
for (int ti = 1; ti <= t; ti++) {
char[] chs = sc.next().toCharArray();
int len = chs.length;
int lastSeen = chs[len-1];
int i = len - 2;
while (i >= 0 && chs[i] >= lastSeen) {
lastSeen = chs[i];
i--;
}
if (i < 0) {
System.out.println("no answer");
continue;
}
Arrays.sort(chs, i+1, len);
int j = i+1;
while ( j < len && chs[j] <= chs[i]) j++;
char temp = chs[i];
chs[i] = chs[j];
chs[j] = temp;
System.out.println(new String(chs));
}
}
}
Approach 2.
import java.io.*;
import java.util.*;
public class Solution {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int T = in.nextInt();
in.nextLine();
while (T-- > 0) {
String s = in.nextLine();
int l = s.length();
char c[] = s.toCharArray();
boolean fix = false;
int startind = -1;
for (int i = l - 1; i >= 0; i--) {
int index = -1;
char min = (char)255;
for (int j = i + 1; j < l; j++)
if (c[j] > c[i] && c[j] < min) {index = j; min = c[j];}
if (index != -1) {char tmp = c[i]; c[i] = c[index]; c[index] = tmp; fix = true; startind = i + 1; break;}
}
if (!fix) {System.out.println("no answer"); continue;}
Arrays.sort(c, startind, l);
String ans = new String(c);
System.out.println(c);
}
}
}
Approach 3.
import java.io.*;
import java.util.*;
public class Solution {
public static void main(String[] args) {
/* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
Scanner scan = new Scanner(System.in);
int n = Integer.parseInt(scan.nextLine());
String [] inputs = new String[n];
for(int i=0;i<n;i++)
{
inputs[i] = scan.nextLine();
}
for(int j=0;j<n;j++)
{
char[] a = inputs[j].toCharArray();
int pivot=-1;
int k=-1;
for(int i=a.length-1; i>0;i--) {
if(a[i] > a[i-1]) {
pivot = i-1;
break;
}
}
if(pivot ==-1)
{ System.out.println("no answer");
continue;
}
for(int i=a.length-1;i>pivot;i--)
{
if(a[i] > a[pivot])
{
k= i;
break;
}
}
char tmp = a[k];
a[k] = a[pivot];
a[pivot] = tmp;
for(int i=1;i<=(a.length-1-pivot)/2;i++) {
tmp = a[pivot+i];
a[pivot+i] = a[a.length-i];
a[a.length-i] = tmp;
}
System.out.println(String.valueOf(a));
}
}
}
Solution in python3
Approach 1.
import sys
from itertools import permutations
def nextperm(w):
for x in range(len(w)-1,0,-1):
if w[x-1]<w[x]:
for y in range(len(w)-1,x-1,-1):
if w[y] > w[x-1]:
return w[:x-1] + w[y:y+1] + w[:y:-1] + w[x-1:x] + w[y-1:x-1:-1]
return "no answer"
t = int(input())
for x in range(t):
w = input()
result = nextperm(w)
print(result)
Approach 2.
for _ in range(int(input())):
s = input()
has_greater = False
for i in range(len(s)-1)[::-1]:
if ord(s[i]) < ord(s[i+1]):
for j in range(i+1,len(s))[::-1]:
if ord(s[i]) < ord(s[j]):
lis = list(s)
lis[i],lis[j]=lis[j],lis[i]
print("".join(lis[:i+1]+lis[i+1:][::-1]))
has_greater = True
if has_greater == True:
break
if has_greater == True:
break
if has_greater == False:
print("no answer")
Approach 3.
for i in range(int(input())):
s = input()
has_greater = False
for i in range(len(s)-1)[::-1]:
if ord(s[i]) < ord(s[i+1]):
for j in range(i+1,len(s))[::-1]:
if ord(s[i]) < ord(s[j]):
lis = list(s)
lis[i],lis[j]=lis[j],lis[i]
print("".join(lis[:i+1]+lis[i+1:][::-1]))
has_greater = True
if has_greater == True:
break
if has_greater == True:
break
if has_greater == False:
print("no answer")
Solution in cpp
Approach 1.
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main() {
int t;cin>>t;
while(t)
{ string str;
cin>>str;
int f= next_permutation(str.begin(),str.end());
if(f==0)
{ cout<<"no answer"<<endl;}
else
{cout<<str<<endl;}
t--;
}
return 0;
}
Approach 2.
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
bool flag = 0;
string str;
long T;
cin>>T;
while(T--)
{
cin>>str;
if(next_permutation(str.begin(),str.end()))
cout<<str<<endl;
else
cout<<"no answer"<<endl;
}
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
return 0;
}
Approach 3.
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
void GetSmallestBigger(const string& input, string& output)
{
output = input;
if (!next_permutation(output.begin(), output.end()))
{
output = "no answer";
}
}
int main()
{
int N = 0;
cin >> N;
for (size_t i = 0; i < N; i++)
{
//string input = "zyyxwwtrrnmlggfeb";
string input;
string output;
cin >> input;
GetSmallestBigger(input, output);
if (i == N - 1)
cout << output;
else
cout << output << endl;
}
return 0;
}