Permutations of a given String

Permutations of a given String

·

1 min read

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));
        }        
    }
}