Problem Link - https://practice.geeksforgeeks.org/problems/permutations-of-a-given-string2041/1
Input: ABC
Output:
ABC ACB BAC BCA CAB CBA
Explanation:
Given string ABC has permutations in 6
forms as ABC, ACB, BAC, BCA, CAB and CBA
Solution:
class Solution {
List<String> list;
public List<String> find_permutation(String S) {
// Code here
list = new ArrayList<String>();
helper("", S);
Collections.sort(list);
return list;
}
void helper(String op, String ip) {
//System.out.println(op);
if(ip.length()==0) {
if(!list.contains(op)) // we want to take care of duplicates
list.add(op);
return;
}
char ch = ip.charAt(0);
for(int i=0; i<=op.length(); i++) {
// taking processed string and adding chars at both side of its each index, that's why loop, and then calling function recursively to keep adding chars in the processed string
String prefix = op.substring(0,i);
String suffix = op.substring(i, op.length());
helper(prefix + ch + suffix, ip.substring(1));
}
}
}