[C] Find next lexicographically greater string

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 the case of multiple possible answers, find the lexicographically smallest one among them.

Example - Let the given word is 'lgeuvf', then the next lexicographically greater is 'lgevfu'. In the case of the word 'ywwwsqonmkjjjec', there is no greater word since it is already the greatest word of the given combination. 

While finding the next greater word, we try to permute the given combination such that there is minimal change and the resulting word is closest to the original word. Find the right-most non-increasing longest (say RNL) sub-string. In 'lgeuvf', 'vf' is the RNL sub-string. However, in 'ywwwsqonmkjjjec' the entire string is the RNL sub-string. Such sub-string is the greatest lexicographical combination and there is no greater string. We mark the character left to the sub-string and call it pivot. The character 'u' is the pivot in 'lgeuvf. Note, 'u' less than 'v'.

Now, we find the right-most character in RNL sub-string which is greater than the pivot. Let's call this RGC. The character 'v' is RGC in above example string. We get the next lexicographically greater word, by swapping the RGC & the pivot and sorting the modified RNL. After swapping RGC & pivot in 'lgeuvf', we get 'lgevuf'. And sorting the modified RNL (which is 'vf'), we get 'lgevfu'.

Following is the C implementation of described algorithm.

#include <stdio.h>;
#include <string.h>;
#include <math.h>;
#include <stdlib.h>;
 
#define NO_ANS "no answer"
#define BUF_SIZE 501
 
int findPivot(char* iStr);
int getModifiedRNL(char* iStr, char);
void swap(char* a, char* b);
char* strPermute(char* iStr);
void quickSort(char* iStr);
void quickSortItr(char* iStr, int start, int end);
 
char* testip[] = {"mqyvczrlabtesyeiteblqklfhkchcryggkewpsfxsumvsjerssbltntydzwrjvf",
"pzxgfnsapnchz",
"erwidqokyjfpctpfxuojyloafghxgifdvhcmzjogoqoikjhjngbhfetvtraaojkfqvyujbhdizrkvqmfpzbidysbkhvuebtr",
"zedawdvyyfumwpupuinbdbfndyehircmylbaowuptgmw",
"zyyxwwtrrnmlggfeb",
"zzzyyyyxxxxwwwwwvvuuuuuuuttttsssrrrqqqqpppooooonnnnmmmllkjjjjiiiiihhhgggfeeeddcccbbbaa",
"lgeuvf",
"ywwwsqonmkjjjec",
"cfvhmxuuvzeycgzltorcfbpqtejfubfpkyqfrugixsvmnyizmzotttyriqpjdwbyoggjgbo",
"zssfzbdeamejrtmqgpywlwwulxerrftkxlvzffztvmfraygtkoeyyitiqgonknchdccjxfqsdgpduuhxatmkdlbww",
"dqwrmse"};
 
char* testop[] = {"mqyvczrlabtesyeiteblqklfhkchcryggkewpsfxsumvsjerssbltntydzwrvfj",
"pzxgfnsapnczh",
"erwidqokyjfpctpfxuojyloafghxgifdvhcmzjogoqoikjhjngbhfetvtraaojkfqvyujbhdizrkvqmfpzbidysbkhvuerbt",
"zedawdvyyfumwpupuinbdbfndyehircmylbaowuptgwm",
"no answer",
"no answer",
"lgevfu",
"no answer",
"cfvhmxuuvzeycgzltorcfbpqtejfubfpkyqfrugixsvmnyizmzotttyriqpjdwbyoggjgob",
"zssfzbdeamejrtmqgpywlwwulxerrftkxlvzffztvmfraygtkoeyyitiqgonknchdccjxfqsdgpduuhxatmkdlwbw",
"dqwrsem"
};
 
 
int main() {
    int N = 11;
 
    for(int indx = 0; indx < N; indx++) {
 
        char* oStr = strPermute(testip[indx]);
  printf("test case %d: ", indx + 1);
  if(strcmp(oStr, testop[indx]) != 0) {
   printf("FAILntinput: %s ntoutput: %sn", testip[indx], oStr);
  } else
   printf("PASSntinput: %s ntoutput: %sn", testip[indx], oStr);
        free(oStr);
 
    }
 
    return 0;
}
 
char* strPermute(char* iStr) {
    char *oStr = NULL;
     
    int fCharIndex = findPivot(iStr);
    if(fCharIndex == -1) {
        oStr = (char*) calloc(strlen(NO_ANS) + 1, sizeof(char));
        memcpy(oStr, NO_ANS, strlen(NO_ANS));
        return oStr;
    }
     
    int sCharIndex = getModifiedRNL(iStr + fCharIndex + 1, iStr[fCharIndex]);
    if(sCharIndex == -1) {
        oStr = (char*) calloc(strlen(NO_ANS) + 1, sizeof(char));
        memcpy(oStr, NO_ANS, strlen(NO_ANS));
        return oStr;
    }
     
    oStr = (char*) calloc(strlen(iStr) + 1, sizeof(char));
    memcpy(oStr, iStr, strlen(iStr));
    swap(oStr + fCharIndex, oStr + fCharIndex + 1 + sCharIndex);
    quickSort(oStr + fCharIndex + 1);
 if(strcmp(iStr, oStr) == 0) {
        memcpy(oStr, NO_ANS, strlen(NO_ANS)+1);
        return oStr;
    }
     
    return oStr;
}
 
int findPivot(char* iStr) {
    if(iStr == NULL || strlen(iStr) == 1)
        return -1;
     
    int isLen = strlen(iStr);
    int indx = isLen - 2;
 while(indx >;= 0 &amp;&amp; iStr[indx] >;= iStr[indx + 1])
  indx--;
 
    return indx;
}
 
int getModifiedRNL(char* iStr, char fChar) {
 int iLen = strlen(iStr);
 if(iLen == 1)
  return 0;
     
    int indx = iLen - 1;
    while(indx >;= 0 &amp;&amp; fChar >;= iStr[indx]) {
  indx--;
    }
 
 return indx;
}
 
void quickSort(char* iStr) {
    quickSortItr(iStr, 0, strlen(iStr) - 1);
}
 
void quickSortItr(char* iStr, int start, int end) {
    if(start >;= end)
        return;
     
    int indx = 0, pIndx = 0;
    while(indx < end) {
        if(iStr[indx] <= iStr[end]) {
            swap(iStr + indx, iStr + pIndx);
            pIndx++;
        }
        indx++;
    }
    swap(iStr + pIndx, iStr + end);
     
    quickSortItr(iStr, start, pIndx - 1);
    quickSortItr(iStr, pIndx + 1, end);
}
 
void swap(char* a, char* b){
    char tmp = *a;
    *a = *b;
    *b = tmp;
}

Compilation on Ubuntu:

   gcc -std=gnu99 strPermute.c -o strPermute 

Output for the test cases.

test case 1: PASS
 input: mqyvczrlabtesyeiteblqklfhkchcryggkewpsfxsumvsjerssbltntydzwrjvf 
 output: mqyvczrlabtesyeiteblqklfhkchcryggkewpsfxsumvsjerssbltntydzwrvfj
test case 2: PASS
 input: pzxgfnsapnchz 
 output: pzxgfnsapnczh
test case 3: PASS
 input: erwidqokyjfpctpfxuojyloafghxgifdvhcmzjogoqoikjhjngbhfetvtraaojkfqvyujbhdizrkvqmfpzbidysbkhvuebtr 
 output: erwidqokyjfpctpfxuojyloafghxgifdvhcmzjogoqoikjhjngbhfetvtraaojkfqvyujbhdizrkvqmfpzbidysbkhvuerbt
test case 4: PASS
 input: zedawdvyyfumwpupuinbdbfndyehircmylbaowuptgmw 
 output: zedawdvyyfumwpupuinbdbfndyehircmylbaowuptgwm
test case 5: PASS
 input: zyyxwwtrrnmlggfeb 
 output: no answer
test case 6: PASS
 input: zzzyyyyxxxxwwwwwvvuuuuuuuttttsssrrrqqqqpppooooonnnnmmmllkjjjjiiiiihhhgggfeeeddcccbbbaa 
 output: no answer
test case 7: PASS
 input: lgeuvf 
 output: lgevfu
test case 8: PASS
 input: ywwwsqonmkjjjec 
 output: no answer
test case 9: PASS
 input: cfvhmxuuvzeycgzltorcfbpqtejfubfpkyqfrugixsvmnyizmzotttyriqpjdwbyoggjgbo 
 output: cfvhmxuuvzeycgzltorcfbpqtejfubfpkyqfrugixsvmnyizmzotttyriqpjdwbyoggjgob
test case 10: PASS
 input: zssfzbdeamejrtmqgpywlwwulxerrftkxlvzffztvmfraygtkoeyyitiqgonknchdccjxfqsdgpduuhxatmkdlbww 
 output: zssfzbdeamejrtmqgpywlwwulxerrftkxlvzffztvmfraygtkoeyyitiqgonknchdccjxfqsdgpduuhxatmkdlwbw
test case 11: PASS
 input: dqwrmse 
 output: dqwrsem