There are man methods and best case complexity is $O(n!)$ as there are $n!$ permutations for a string. I'm using Java code as it is recommended for most top tier interviews. (C is not suitable for many interviews as in Google).
Here permute and permute1 are two different permutation methods.
import java.io.*;
import java.util.ArrayList;
public class permuteString{
ArrayList<String> permute(String str){
ArrayList<String> al = new ArrayList<String>();
if(str.length() == 0)
{
al.add("");
return al;
}
ArrayList<String> words = permute(str.substring(1, str.length()));
char c = str.charAt(0);
for(String word: words)
{
for(int i = 0; i<= word.length(); i++)
al.add(word.substring(0, i)+ c+ word.substring(i, word.length()));
}
return al ;
}
void permute1(String prefix, String s) {
if(s.length() == 0)
{
System.out.println(prefix);
}
for(int i =0; i < s.length(); i++)
{
permute1(prefix+s.charAt(i), s.substring(0,i)+s.substring(i+1, s.length()));
}
}
public static void main(String args[]) {
permuteString mystring = new permuteString(); //Initialize class
mystring.permute1("", args[0]);
System.out.println("____________________________");
ArrayList<String> words = mystring.permute(args[0]);
for(String word:words)
System.out.println(word);
}
}