# Next Permutation

Difficulty Level Medium
String

In the next permutation problem we have given a word, find the lexicographically greater_permutation of it.

## Example

```input : str = "tutorialcup"
output : tutorialpcu

input : str = "nmhdgfecba"
output : nmheabcdfg

input : str = "algorithms"
output : algorithsm

input : str = "spoonfeed"
output : Next Permutation Doesnt exist

```

## Lexicographical Order

All the permutations of a word when arranged in a dictionary, the order of words so obtained is called lexicographical order.

Ex :

```word = 'cat'
lexicographical order of permutations of 'cat' :

act
atc
cat
cta
tac
tca```

we can see, ‘cat’ is lexicographically greater than ‘act’.

## Algorithm for Next Permutation

For a word that is completely sorted in descending order, ex: ”nmhgfedcba” doesn’t have the next permutation. We can find the next permutation for a word that is not completely sorted in descending order. ex : “nmhdgfecba”.Below is the algorithm:
Given : str = “nmhdgfecba”

1. Traverse from the right of the string and look for the first character that does not follow the descending order. ‘d’ in str doesn’t follow descending order. index of ‘d’ = 3.
2. To the right of ‘d’, search for the character that is just (or closest) greater than ‘d’ in ASCII value. ‘e’ in [nmhd]gfecba is just greater than ‘d’.This is done using binarySearch() function.
3. swap ‘e’ and ‘d’.The resulting string is “nmhegfdcba”.
4. Now reverse (done using the reverse() function) the part of resulting string occurring after the index found in step 1. reverse “gfdcba” and append it back to the main string.
5. output = “nmheabcdfg”,it is the lexicographically next permutation of  “nmhgfedcba”. Longest Common Prefix using Trie

## Implementation for Next Permutation

### C++ Program

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

// function to reverse the string between index l and r
void reverse(string &str,int l,int r)
{
while(l < r)
swap(str[l++],str[r--]);
}

// function to search a character lying between index l and r
// which is closest greater (just greater) than val
// and return it's index
int binarySearch(string& str,int l,int r,char val)
{
int index = -1;

while (l <= r)
{
int mid = (l+r)/2;
if (str[mid] <= val)
{
r = mid - 1;
}
else
{
l = mid + 1;
if (index == -1 || str[index] >= str[mid])
index = mid;
}
}
return index;
}

// this function generates next permutation (if there exists any such permutation) from the given string
// and returns True
// Else returns false
bool nextPermutation(string& str)
{
int len = str.length();
int i = len-2;

while (i >= 0 && str[i] >= str[i+1])
i--;

if (i < 0)
return false;
else
{
int index = binarySearch(str,i+1,len-1,str[i]);
swap(str[i],str[index]);
reverse(str,i+1,len-1);
return true;
}
}

// main function to find next permutation
int main()
{
string str = "nmhdgfecba";
bool is = nextPermutation(str);

if(is == false)
cout<< "Next Permutation Doesnt exist" <<endl;
else
cout<<str<<endl;

return 0;
}
```
```nmheabcdfg
```

### Java Program

```class permutation
{
// swap two characters of string
static void swap(StringBuilder sb,int l,int r)
{
char temp = sb.charAt(l);
sb.setCharAt(l,sb.charAt(r));
sb.setCharAt(r,temp);
}

// function to reverse the string between index l and r
static void reverse(StringBuilder sb,int l,int r)
{
while(l < r)
{
swap(sb,l,r);
l++;
r--;
}
}

// function to search a character lying between index l and r
// which is closest greater (just greater) than val
// and return it's index
static int binarySearch(StringBuilder sb,int l,int r,char val)
{
int index = -1;

while (l <= r)
{
int mid = (l+r)/2;
if (sb.charAt(mid) <= val)
{
r = mid - 1;
}
else
{
l = mid + 1;
if (index == -1 || sb.charAt(index) >= sb.charAt(mid))
index = mid;
}
}
return index;
}

// this function generates next permutation (if there exists any such permutation) from the given string
// and returns True
// Else returns false
static boolean nextPermutation(StringBuilder sb)
{
int len = sb.length();
int i = len-2;

while (i >= 0 && sb.charAt(i) >= sb.charAt(i+1))
i--;

if (i < 0)
return false;
else
{
int index = binarySearch(sb,i+1,len-1,sb.charAt(i));
swap(sb,i,index);
reverse(sb,i+1,len-1);
return true;
}
}

// main function to find next permutation
public static void main(String args[])
{
String str = "nmhdgfecba";
// strings in java are immutable,so we convert strings into StringBuilder
// StringBuilder are mutable strings
StringBuilder sb = new StringBuilder(str);

boolean is = nextPermutation(sb);

if(is == false)
System.out.println("Next Permutation Doesnt exist");
else
System.out.println(sb);

}
}```
```nmheabcdfg
```

## Next Permutation using STL library

STL library of C++ contains function next_permutation() that generates the next permutation of given string

```#include <iostream>
#include <bits/stdc++.h>    // STL library of C++
using namespace std;

int main()
{
string str = "nmhdgfecba";

// next_permutation() is present in STL library
// next_permutation() generates Next Permutation of a string if it exists
// and returns true
// else returns false
if(next_permutation(str.begin(),str.end()))
cout<<str<<endl;
else
cout<<"Next Permutation Doesnt exist";

return 0;
}```
`nmheabcdfg`

## Complexity Analysis

1. Time Complexity: Overall Time complexity T(n) = O(n)
• In the worst case, the first step of nextPermutation() takes O(n) time.
• binarySearch() takes O(logn) time.
• reverse() takes O(n) time.
2. Space Complexity: A(n) = O(1) because here we don’t use any auxiliary space during computation of the task. That’ s means the space complexity of next permutation problem, in this case, is constant.