Bigger is Greater Hackerrank problem solution

Bigger is Greater Hackerrank

We had played a lot with numbers, not even played we are still playing with them but today we have to solve a problem of letters. The problem is based on rearranging the letters and we have some given condition. So the conditions are: Given a word ‘w’, we have to rearrange the letters of ‘w’ to construct another word in such a way that ‘s’ is lexicographically greater than ‘w’. If you found more than one answer to the above problem then, in that case, find the lexicographically smallest one among them.

Conditions to test:

Input Format

The first line of input contains t, the number of test cases. Each of the next t lines contains w.

Constraints

1<=t<=105
1<=|w|<=100

w will contain only lower-case English letters and its length will not exceed 100.
Output Format

For each test case, output a string lexicographically bigger than ‘w’ in a separate line. In case of multiple possible answers, print the lexicographically smallest one, and if no answer exists, print no answer.

Sample Input

5
ab
bb
hefg
dhck
dkhc
Sample Output

ba
no answer
hegf
dhkc
hcdk
Explanation

Test case 1:
There exists only one string greater than ab which can be built by rearranging ab. That is ba.
Test case 2:
Not possible to rearrange bb and get a lexicographically greater string.
Test case 3:
hegf is the next string lexicographically greater than hefg.
Test case 4:
dhkc is the next string lexicographically greater than dhck.
Test case 5:
hcdk is the next string lexicographically greater than dkhc.

solution

We can find the next largest lexicographic string for a given string S using the following step.
Iterating over every character, we will get the last value i (starting from the first character) that satisfies the given condition
S[i] < S[i + 1]
Now, we will get the last value j such that
S[i] < S[j]
We now interchange S[i] and S[j]. And for every character from i+1 till the end, we sort the characters. i.e.,
sort(S[i+1]..S[len(S) – 1])
The given string is the next largest lexicographic string of S.
One can also use next_permutation function call in cpp.

#include <bits/stdc++.h>
using namespace std;

int main(){
    int test;
    cin >> test;
    while(test--) {
        string inp;
        cin >> inp;
        if (next_permutation(inp.begin(), inp.end()) == false ) {
            cout << "no answer" << endl;
        }
        else {
            cout << inp << endl;
        }
    }
    return 0;
}
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */  
    vector<string> st;
int n;
cin >> n;
for (int i = 0; i < n; ++i)
{
    string s;
    cin >> s;
    st.push_back(s);
}
for (int i = 0; i < n; ++i)
{
    string temp = st[i];
    string ans;
    do
    {   

        next_permutation(st[i].begin(), st[i].end());

        if (temp < st[i])
        {
            ans = st[i];
        }
        temp = st[i];

    } while (st[i] != temp);

    if (ans.empty())
    {
        cout << "no answer" << endl;
    }
    else
        cout << ans << endl;
}
    return 0;
}t = input()
for _ in range(t):
    word = list(raw_input().strip())
    start = -1
    for i in xrange(0, len(word) - 1):
        if word[i] < word[i + 1]:
            start = i

    if start == -1:
        print "no answer"
        continue

    end = -1
    for j in xrange(start + 1, len(word)):
        if word[start] < word[j]:
            end = j

    word[start], word[end] = word[end], word[start]
    a = word[start + 1:]
    a.sort()

    for j in xrange(start + 1, len(word)):
        word[j] = a[j - start - 1]

    print "".join(word)

 

Note: All rights reserved. No part of this Post may be copied, distributed, or transmitted in any form or by any means, without the prior written permission of the website admin, except in the case of brief quotations embodied in critical reviews and certain other noncommercial uses permitted by copyright law. For permission requests, write to the owner, addressed “Attention: Permissions Coordinator,” to the admin@coderinme.com

A web developer(Front end and Back end), and DBA at csdamu.com. Currently working as Salesforce Developer @ Tech Matrix IT Consulting Private Limited. Check me @about.me/s.saifi

Leave a reply:

Your email address will not be published.