Category: algorithms

How to find permutations of a String using recursion in Java ?

In this blog we are going to find out all the permutations of a given string. Like always, we will first start from the basics – Understand what is a permutation of a string, break the procedure down into smaller steps and understand the procedure of finding out one permutation. Finally, we will write code in Java for the same. Along the way, I will also be explaining each line code and show you pictorial representations of the code execution so that you can visualize it better.

What is a permutation ?

Different ways of arranging a set of items is permutation. A string is a sequence of characters. Permutation of a string is arranging the characters of the string in different ways. Let’s take an example to understand this.

Permutation of a String

The string “ace” can be arranged as “ace”, “aec”, “cae”, “cea”, “eac”,”eca” – different arrangements of the characters a,c,e which make the string “ace”. Note that the string “ace” is of length 3 and we get 6 different permutations of the same – 3 factorial. If the input string was “aced”, we will get 24 permutations – 4 !

Observation about the permutations

Did you notice that the first 2 permutations “ace”, “aec” have a as the first letter and the 2 other letters are then concatenated to the letter a.

Extracting the first character ‘a’ from “ace” leaves us with the remaining characters “ce”. It can be rearranged as “ce” , “ec”. Finally appending each to “a” results in “ace” and “aec“.

If we single out the character ‘c’ in ace, we are left with “ae”. With “ae”, rearranging them gives us “ae” and “ea”. Appending this to ‘c’ results in “cae” and “cea“.

If we single out the character ‘e’ in ace, we are left with “ac”. With “ac”, rearranging them results in “ac” and “ca”. Appending this to ‘e’ results in “eac” and “eca“.

Translating these observations into a technical perspective

We are taking a single character from the given string, starting with ‘a’, moving on to ‘c’ and finally visiting ‘e’. This can be done using the charAt function. We also need a for loop as we need to single out each character from the string.

for(int i = 0; i < remainingString.length();i++) {
    char ch = remainingString.charAt(i);
    ...
}

For each character that we extract, we need the rest of the string. So when we extract ‘a’ from the “ace”, we need “ce” so that we can have different arrangements of “ce” to append it to ‘a’. When we extract ‘c’ from “ace”, we need “ae”. When we extract ‘e’ from “ace”, we need “ac”. In short, when we are at a particular iteration , i , in the for loop, we need a string from the characters before and after that character.

How do we extract the remaining characters ?

We make use of the substring function to do that. The variable ‘i’ in the for loop points to current single character that we extract. When we extract ‘c’ from “ace”, we need to get “ae”. We can get all characters before i by making a call to substring(0,i) and everything after i by calling substring(i+1). We append them to get the remaining string.

When i =1 and ‘c’ is extracted
for(int i = 0; i < remainingString.length();i++) {
    char ch = remainingString.charAt(i);
    String next = remainingString.substring(0,i)  + 
                  remainingString.substring(i+1);
    ...
}
Applying recursion

What is clear so far is that we start with the first character and apply permutation with remaining characters. Then we choose the second character and apply permutation with remaining characters. We continue this way until we visit each character in the string. To do something like this, recursion can be a good choice.

So let us take the code above and add it to a function, permutations.

public void permutations(String remainingString , String permutation) {
    for(int i = 0; i < remainingString.length();i++) {
        char ch = remainingString.charAt(i);
        String next = remainingString.substring(0,i)  + 
                      remainingString.substring(i+1);
        //Code here for recursive call to permutations
       }
}

This function takes 2 parameters – remainingString and permutation. Why do we need them ? Well, the parameter remainingString keeps track of length of string to produce one complete permutation of current string.The permutation parameter will keep track of the current permutation.The first time this code starts executing, the remainingString will be the input string, “ace”, and the permutation will be a blank string, “”, since we are yet to start finding permutations. Now we start with ‘a’,fix that and then extract “ce”. So ‘a’ will be stored in ch and “ce” will be stored in variable referred to as next.

What do we have so far ?

remainingString = “ace”, permutation = “”, ch = ‘a’, next = “ce”

What should the next step be?

The variable, permutation, so far is “”, it should be “a”. It is not a valid end permutation but an intermediate one. The current value is a “”. Appending “” to “a” gives us “a”. So let’s define a variable permute and assign it to permutation +ch. 

            String permute = permutation+ch;

So the variable permute = “” + “a” = “a”

public void permutations(String remainingString , String permutation) {
    for(int i = 0; i < remainingString.length();i++) {
        char ch = remainingString.charAt(i);
        String permute = permutation+ch;
        String next = remainingString.substring(0,i)  + 
                      remainingString.substring(i+1);
        //Code here for recursive call to permutations
       }
}

Now, remainingString = “ace”, permutation = “”, ch = ‘a’, next = “ce”, permute =”a”

The next logical step is working on “ce” to extract ‘c’. Once that is done, the intermediate permutation is “ac”. “a” from the previous iteration and ‘c’ extract from current one. When we extract ‘c’ from “ce”, what remains is “e”. This is the same sequence as previous steps.

The solution seems to repeat for the next sub-problem. This can be solved by recursion. We need to call the permutations function. It takes 2 parameters – remainingString and permutation. The variable, next, has value “ce” and permutation currently is “a”. Let’s make a call to permutations function and pass these parameters.

public void permutations(String remainingString , String permutation) {
    for(int i = 0; i < remainingString.length();i++) {
        char ch = remainingString.charAt(i);
        String permute = permutation+ch;
        String next = remainingString.substring(0,i)  + 
                      remainingString.substring(i+1);
        //Code here for recursive call to permutations
        permutations(next,permute);
       }
}

After the first recursive call, remainingString = “ce”, permutation = “a”. When code above starts execution, i = 0 , ch = ‘c’ , permute = “a” + ‘c’ = “ac” , next = “e”. Note that when this call happens, i = 0 . This block will get executed twice as the for loop checks for length of remainingString. More on this later. Then there is a recursive call again to the function by passing “e”, “ac”.

In the next iteration, remainingString = “e”, permutation = “ac”. When the code starts executing, i = 0 , ch = ‘e’ , permute = “ace” , next = “”. Then there is a call to recursive function with “” and “ace”.

Now , remainingString = “” , permutation =”ace”. It looks like the remainingString is a blank string along with the fact that permutation is “ace”. We are in a recursive function, every recursive function should have some condition to return if it has processed it’s sub-problem. This part is now solved, isn’t it ? So we need a terminating condition – the length of the variable, remainingString, can be that condition. We simply check if it’s length is zero.

public void permutations(String remainingString , String permutation) {
    if(remainingString.length() == 0 ) {
        System.out.println(permutation);
        return ;
    }

    for(int i = 0; i < remainingString.length();i++) {
        char ch = remainingString.charAt(i);
        String permute = permutation+ch;
        String next = remainingString.substring(0,i)  + 
                      remainingString.substring(i+1);
        permutations(next,permute);
       }
   }

After the execution of this code we get “ace” and this function returns. The code execution continues from the the location that it was called – this is really the previous step. Take a look at the following flows to get a better understanding. Start from the block which says start and then the steps have been numbered.Push and pop indicates recursive function calls and returning back from a function.

Snapshot of the function calls when i = 0 and input is “ace”
Produces 2 permutations “ace” and “aec”

Step 1 will get executed twice as length of “ce” is 2. When i is 0, we get “ace” and when i =1 , we get “aec”. When the function returns from step 2, we go back to step 1 where i will become 1. This will cause step 4 to be executed.

Note that, all these steps are happening when input is “ace” and i = 0. When i =1, a similar set of steps will be executed producing 2 more permutations.

Snapshot of the function calls when i = 1 and input is “ace”
Produces 2 permutations “cae” and “cea”
Snapshot of the functional calls when i = 2 and input is “ace”
Produces 2 permutations “eac” and “eca”

The images below will give you a more detailed view of how the code and function calls execute. We call the function, permutations, pass the parameters “ace” and “”.

Snapshot of the code execution when input is “ace” and i=0
These steps produce 2 permutations – ace and aec as seen in steps 3 and 5
Snapshot of the code execution when input is “ace” and i=1
These steps produce 2 permutations – cae and cea as seen in steps 8 and 10

I have left out the code tracing when i=2, it can be a good exercise for you.

Conclusion

The number of lines of code that we had to write to produce the permutations is small but there is a lot that is happening behind the scenes.Such kind of problems are being asked in technical interviews. Irrespective of this, I think recursion is an important concept to understand and it is also a good fit for a good number of problems.

Recursion is not very straight forward to understand but I hope the pictorial representations and breaking up the code step by step have given you a good understanding of the same. I urge you to take a piece of paper and trace the execution for one particular iteration – this will not only solidify your understanding of the solution to the permutation problem but help you sharpen your skill set by understanding recursion.

How to find all duplicates in an array – Java and Kotlin

During a conversation with my colleague, he mentioned to me about a problem that he was asked in his technical interview. The problem was to find the duplicates in an array of integers. My immediate reaction – “That is easy and I am sure you got it !” But just then there was a two second silence from his end and then he said that he couldn’t get it right since some additional constraints were mentioned to him ‘later’.

Problem Statement

Find the elements which appear twice in an array of integers, where the elements in the array being : 1 ≤ a[i] ≤ n (n = size of array). We need to do this without using additional space in O(n) runtime.

Solution

Now, it was my turn to be silent for the next couple of seconds after he told me about the problem statement with the constraints about not using additional space and O(n) runtime.

We had a discussion about using a Set or may be a HashMap in Java since the main part of the problem was to find the “duplicates”. Using a Set or a Map would not be the right solution with these constraints. A nested for loop would also not be the right solution since we need to solve the problem in O(n) runtime. Well, let’s consider some sample data and try solving this step by step.

Sample Input data

The output for this input will be 10 and 1. They both appear twice. Note that the length of the array is 10 and the maximum value of any element in the array is <=10. This is an important constraint.

Let us solve this step by step
Elements of array, arr, where iteration starts at 0
  1. Loop through the array and for each iteration-
    1. Take the value at each index. Currently at 0, in the first iteration, the value will be 10
    2. Subtract one from this value. During iteration 0, the result will be 9. The reason we subtract one is because the value of any element in the array is <=n, where is n is size of the array. The array index starts from 0. So an array of size 10 can contain a maximum value of 10 but there is no arr[10].
    3. Use this result as an index. For iteration 0, this will be 9, go to element number 9 and negate the value at this index number 9
Why should we do this and what about the duplicates ?

Well, if we encounter another value of 10 in this array, the index obtained using steps above will result in 9 again. We access to value at 9th position which is -7 now. We check if this is less than 0 and if it is less than 0, it means we have already visited the ‘value at this current iteration‘. This means it is a duplicate value. So step 3 in the algorithm above can be modified as follows:

Loop through the array and for each element in the array, let’s refer to the array as arr, do the following –

  1. Take the value at each iteration. Currently at 0 in the first iteration, the value will be arr[0] which is 10.
  2. Subtract one from this, the value will be 9. Let us refer to this value as index.
  3. Using this index, access the value at this index, element at index 9, arr[9]. If the value at this index is less than 0, add arr[current_iteration] to the list of duplicate elements.
  4. Negate the value at this index.(currently 9 for this iteration 0)
  5. Go back to step 1, the next iteration which is current_iteration + 1.
Flowchart
Iteration 0
Iteration 1
Iteration 2
Iteration 3
Iteration 4

In this iteration number 4, when we access the value at arr[4], we get a -9. If we were to follow step 2 of the algorithm, we would land up with an index of -10 and then in step 3 we would access arr[-10] which is incorrect. So we need to modify the algorithm to take absolute value of the same.

Iteration 5
Iteration 6
Iteration 7
Iteration 8
Iteration 9 (Final iteration)
Java Code
import java.util.ArrayList;
import java.util.List;

public class DuplicatesInArray {

    public static List<Integer> findDuplicates(int arr[]) {
        List<Integer> duplicates = new ArrayList<>();
        for (int i = 0; i < arr.length; i++) {
            int index = Math.abs(arr[i]) - 1;
            if (arr[index] < 0){
                duplicates.add(Math.abs(arr[i]));
            }
            arr[index] = -arr[index];
        }
        return duplicates;
    }

    public static void main(String[] args) {
        int [] arr = {10,2,5,10,9,1,1,4,3,7};

        List<Integer> duplicates = findDuplicates(arr);
        System.out.println(duplicates);
    }
}

The Math.abs is required since we could have negated the value at an index in a previous iteration. If we don’t do a Math.abs, we will land up accessing arr[-index]. For the same reason, Math.abs is also required while adding an element to the list of duplicate values.

Kotlin code
fun findDuplicates(arr:IntArray) : List<Int>{

    var duplicates  = arrayListOf<Int>()
    for(itemIndex in arr.indices){

        val goToIndex = Math.abs(arr[itemIndex]) - 1

        if(arr[goToIndex] < 0 ){
            duplicates.add(Math.abs(arr[itemIndex]))
        }

        arr[goToIndex] = -arr[goToIndex]
    }
    return duplicates
}

fun main(){
    var arr = intArrayOf(10,2,5,10,9,1,1,4,3,7)
    println(findDuplicates(arr))
}
Conclusion

We have traversed the entire array and the list of duplicates has 2 elements: 10 and 1. The flip side of this algorithm is that the elements of the array are modified but we have not used any additional storage. We have also managed to do this in O(n) as this is just a single pass of entire array.

The code in Java and Kotlin is quite simple but you need to know the algorithm/solution for this particular problem before hand. This problem is an interesting one given the constraints of space and time but I don’t think the solution was so straight forward. In my opinion, I don’t think the outcome of a technical interview should be decide based on just this problem.