Skip to main content

Lexicographical permutations

· 4 min read
Matej Jelluš
IT enthusiast that loves to write code and trying new things. Currently working in Bratislava as CTO in Kontentino.

The solution for Bigger is Greater challenge on HackerRank, or how to generate next lexicographically greater string. Problem description, algorithm steps and complete source code to solve this challenge.

From time to time I am solving “challenges” in my free time on Project Euler or HackerRank. This time it was the challenge Bigger is Greater on HackerRank. It’s about finding next lexicographically greater string than the given string.

Problem

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 among them.

Input

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

5
ab
bb
hefg
dhck
dkhc

Output

For each testcase, 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.

ba
no answer
hegf
dhkc
hcdk

Solution in C++

Steps

Here are the steps / algorithm to generate the next higher permutation :

  1. take the string and find highest index i that string[i] < string[i + 1]
  2. find the highest index j > i such that string[j] > string[i]
  3. swap string[i] with string[j]
  4. reverse the order of all elements after index i

Source code

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;

int compare (const void *a, const void * b) {
return ( *(char *)a - *(char *)b );
}

void swap (char* a, char* b) {
char t = *a;
*a = *b;
*b = t;
}

int findCeil (char str[], char first, int l, int h) {
int ceilIndex = l;

for( int i = l+1; i <= h; i++ ) {
if( str[i] > first && str[i] < str[ceilIndex] ) {
ceilIndex = i;
}
}

return ceilIndex;
}

bool nextPermutation(char* str) {
int size = strlen(str);

int i;
for ( i = size - 2; i >= 0; --i ) {
if( str[i] < str[i + 1] ) {
break;
}
}

if( i == -1 ) {
return false;
} else {
int ceilIndex = findCeil( str, str[i], i + 1, size - 1 );

swap( &str[i], &str[ceilIndex] );

qsort( str + i + 1, size - i - 1, sizeof(str[0]), compare );
}
return true;
}

int main() {
int tests;
cin >> tests;

string str;
for( int i = 0; i < tests; i++ ) {
cin >> str;
char *cstr = new char[str.length() + 1];
strcpy(cstr, str.c_str());
if( nextPermutation(cstr) ) {
cout << cstr << "\n";
} else {
cout << "no answer\n";
}
}

return 0;
}

Source code #2

There is a Need help? section on the right side of the HackerRank challenge and it recommends Next permutation topic. You can read that in most languages there is the next permutation function already implemented. In C++ it is next_permutation.

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;

int main() {
int tests;
cin >> tests;

string str;
for( int i = 0; i < tests; i++ ) {
cin >> str;
if( next_permutation(str.begin(), str.end()) != 0 ) {
cout << str << "\n";
} else {
cout << "no answer" << "\n";
}
}

return 0;
}

Conclusion

These are two working examples how you can solve the problem above. You can read more about lexicographic permutations on pages below in References section.

References

GeeksforGeeks - Print all permutations in sorted ( lexicographic ) order

Wikipedia - Leicographical order


Do you like this post? Is it helpful? I am always learning and trying new technologies, processes and approaches. When I struggle with something and finally manage to solve it, I share my experience. If you want to support me, please use button below. If you have any questions or comments, please reach me via email juffalow@juffalow.com.

I am also available as a mentor if you need help with your architecture, engineering team or if you are looking for an experienced person to validate your thoughts.