Next lexicographic string permutation

Question: Given a string, find the next lexicographic permutation.

Input: abc
Output: acb

First of all let us try to understand what do you mean by next lexicographic string. To get a hold of the concept try to remember an English dictionary and how words are arranged in it. We start with the letter ‘a’, write all the words and then move to letter ‘b’ all the way to letter ‘z’. This is called as a lexicographic order.
This is possible when we have all the letters in English alphabet available to us. To think upon the question, let us assume that we only have the following letters available.

Letters:– a, b, c
The lexicographic order would be
abc
acb
bac
bca
cab
cba

Thus, ‘acb‘ is the next lexicogrpahic permutation of ‘abc‘. Also note that we cannot form any other word with the letters after ‘cba‘.
To find the next lexicographic string, we can follow a naive approach to generate all the possible permutations of a given string, and then find the next one based upon our input. But this approach can take a lot of time.

Let us try an efficient approach. Here ‘s’ is our string and when we refer to s[i], we are referring to the ascii value of the character. For understanding the problem let us suppose that all the characters in the string are either lowercase or uppercase characters.

1. Find the highest index i such that s[i] < s[i+1]. If no such index exists, then this permutation is the last permutation.
2. Find the highest index j > i such that s[j] > s[i]. Such a j must exist, since i+1 is such an index.
3. Swap s[i] with s[j].
4. Reverse the order of all of the elements after index i till the last element.

You can also refer to this Wikipedia article for more details on the approach.

Here is the sample code:-

class NextPermutation {

  public static void nextPermutation(int[] num) {
    int n = num.length;
    if (n < 2)
      return;
    int index = n - 1;
    while (index > 0) {
      if (num[index - 1] < num[index])
        break;
      index--;
    }
    if (index == 0) {
      reverseSort(num, 0, n - 1);
      return;
    } else {
      int val = num[index - 1];
      int j = n - 1;
      while (j >= index) {
        if (num[j] < val)
          break;
        j--;
      }
      swap(num, j, index - 1);
      reverseSort(num, index, n - 1);
      return;
    }
  }

  public static void swap(int[] num, int i, int j) {
    int temp = 0;
    temp = num[i];
    num[i] = num[j];
    num[j] = temp;
  }

  public static void reverseSort(int[] num, int start, int end) {
    if (start > end)
      return;
    for (int i = start; i <= (end + start) / 2; i++)
      swap(num, i, start + end - i);
  }

  public static void main(String[] args) {
    String s = "abc";
    int[] x = new int[s.length()];
    for (int i = 0; i < s.length(); i++) {
      x[i] = s.charAt(i);
    }
    nextPermutation(x);

    for (int i : x) {
      System.out.print((char) i);
    }
  }
}
Code language: Java (java)

A working implementation of the code can be found here.