dynamic programming – Java2Blog

Minimum Number of Jumps to reach last Index

Java2blog — Thu, 18 Apr 2019 16:25:04 +0000

If you want to practice data structure and algorithm programs, you can go through Java coding interview questions.

In this post, we will see how to find Minimum Number of Jumps to reach last Index.

Problem

Given an array A of positive integers possibly zeroes, every index indicating the maximum length of a jump that can be made from this index. The length of a jump can vary from 1 to A[index].
If value on any index is zero, this means that you can not move forward from this index.
Find the minimum number of jumps required to reach the last index. If the answer is not possible for any case, print “Not Possible”.

Input :
int[] A = { 2, 3, 1, 1, 4 }
Output :
2

Input :
int[] A = { 2, 0, 0, 1, 4 }

Output :
Not Possible

Solution

APPROACH – I :
A basic brute force solution can be achieved by using a recursive approach and making calls to every possible reachable index from the current index.
Now, what does that mean?

We are given the array where each index contains the length of the maximum jumps that can be made from that index.
For eg if A[i] = x, this means that from index ‘i’ we can jump to index i+0, i+1, i+2 … i+x and obviously only if these indices are in bounds.
Here making a call is equivalent to a jump for which we need to keep a jump variable in the function call and increment it in every recursive call made.
The base case condition will be, when the current index in the function call is eventually the end index. In the base case we compare the number of jumps made to reach this end index with the global minimum variable update it if the current number of jumps made to reach end index is less than the previously global minimum jump and return from the current call. If the current index becomes greater than the last index, then return from the current call as this is not the result we are looking for.

Steps:

Start from index zero and initialize the number of jumps made variable to 0.
Now for every index that is, in every call, start a loop from 1 to value at current index in the given array indicating the lengths of jump to be made in the next call. Make the function call with current index incremented by the length of jump and number of jumps by 1.
When in base case, that is, when the current index in the call is equal to the last index, compare the number of jumps with the global min jumps variable, update it if the number of jumps made in this call is less than the previously global minimum jump and return from the current call.
Here we will be using reactive recursive calls, so when the current index in the call is greater than the last index, we simply return from the call without doing any comparisons.

Time Complexity Discussion:
For an array of length n, at every index ‘i’ we are making A[i] jumps which in the worst case can be equal to n. Hence, there can be a total of ‘n’ potential calls from all the ‘n’ indices, therefore the worst time complexity of this solution is O(n^n).

package Backtracking;

public class minJumpsArr {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] A = { 2, 3, 1, 1, 4 };
        /*current index and number of jumps are zero initially*/
        solve(0, A, 0);

        if(minJumps == (int) 1e9 + 1)
        {
            /*if the min jumps is still infinity, this means it has
             * never been updated that is, we did not reach the end
             * index even once, hence answer is not possible in this
             * case*/
            System.out.println("Not Possible");
        }
        else {
            System.out.println(minJumps);
        }

    }

    /* global min variable to store the minimum number of
     * jumps required to reach last index.*/
    public static int minJumps = (int) 1e9 + 1;

    public static void solve(int currIdx, int[] a, int jumps) {
        /* base case : Case 1 - if current index is equal to last
         * index (destination) update the global min jumps if the
         * current number of jumps is lesser and return. 
         * Case 2 - if current index is greater than the last index,
         * simply return because this is not the result we are looking for*/
        if (currIdx >= a.length - 1) {
            if (currIdx == a.length - 1) {
                minJumps = Math.min(minJumps, jumps);
            }
            return;
        }
        /*maximum length of any jump that can be made from this index*/
        int reachableIdxs = a[currIdx];

        /* recursive calls for all lengths of jump varying from 1 to max
         * length and incrementing number of jumps by 1 in every call */
        for (int jumpLength = 1; jumpLength <= reachableIdxs; jumpLength++) {
            solve(currIdx + jumpLength, a, jumps + 1);
        }
    }

APPROACH 2 :

In the above recursive solution, we can clearly see a lot of redundant calls, therefore for the reduction of the number of calls and eventually for reduced time complexity, we can use Dynamic programming approach.

For any index ‘i’ we can actually store the minimum number of jumps required to reach this index and then from here we can calculate the same for all the reachable indices from this index ‘i’ (‘reachable indices’ term is explained in the previous approach).
Now for any current index, the minimum number of jumps required to reach any ‘reachable index’ from start(‘0’ th index) is minimum jumps required to reach this current ‘i’th index from start(‘0’ th index) + 1 (to reach index ‘i+x’ directly from index ‘i’) , that is,
minJumps[i+x] = minJumps[i] + 1
Where, x can be 1, 2, 3…A[i]
Possibly We will be reaching the same index more than once with different number of jumps, but we want the minimum value, therefore, we update any minJumps[i] only if the current number of jumps required to reach ‘i’ is less then the current value at minJumps[i]

Time Complexity Discussion :
Again in this approach, from any index ‘i’ we are calculating minimum number of jumps of all the reachable indices by visiting all the reachable indices from any index, which can be ‘n’ in a worst case, and we are doing this for all n indices.
Therefore, the time complexity of this algorithm is O(n^2).

import java.util.Arrays;

public class minJumpsArr {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] A = { 2, 0, 1, 1, 4 };

        int ans = solveDP(A);
        if(ans == Integer.MAX_VALUE)
        {
            /* if the min jumps for the last index is still infinity,
             * this means it has never been updated that is, we did
             * not reach the end index even once, hence answer is not
             * possible in this case*/
            System.out.println("Not Possible");
        }
        else {
            System.out.println(ans);
        }

    }

    public static int solveDP(int[] a) {
        int[] minJumps = new int[a.length];
        /*
         * initialize min Jumps for every index to infinity
         * as the minimum value is to  be calculated for
         * every index
         */
        Arrays.fill(minJumps, Integer.MAX_VALUE);
        /* minimum jumps required to reach the very first index is zero */
        minJumps[0] = 0;

        /*calculating min jumps for every index */
        for (int i = 0; i < a.length; i++) {
            /* maximum length of jump from this index or the maximum
             * reachable index from this index*/
            int maxJump = a[i];
            for (int j = 1; j <= maxJump; j++) {
                /*visiting all the reachable index*/
                int reachableIdx = i + j;
                /* updating the minimum jumps required for every reachable
                 * index but only if the reachable index is in bounds and
                 * the intermediate index from which we are making jump to
                 * this reachable index must also be reachable from zeroth
                 * index*/
                if (reachableIdx < a.length && minJumps[i] != Integer.MAX_VALUE) {
                    /* min jumps for every reachable index is min jumps for this
                     * intermediate index 'i' + 1 ( for the jump from intermediate
                     * index to this reachable index) */
                minJumps[reachableIdx] = Math.min(minJumps[reachableIdx], minJumps[i] + 1);
                }
            }
        }
        /*finally return the minimum jumps required to reach last index*/
        return minJumps[a.length-1];
    }

Before moving on to the next approach, just think if we could do better by using a greedy approach and making greedy coices for next index to jump on, rather than exploring all the possibilities using Dynamic programming.

Approach – III :
Yes we can definitely solve the given problem more efficiently by adopting a greedy approach.

The basic strategy would be to keep the track of Maximum reachable index the whole time which will eventually be updated frequently as we move through the given array and as soon as we reach this Maximum reachable index, we increment our number of jumps.
For this, we maintain 2 variables which stores the value of current index and Maximum reachable index. The very first thing we do after reaching any index is update the value of Maximum reachable index by comparing it with current Index + A[current Index] (indicating the maximum length of any jump that can be made from here) and we upadate Maximum reachable index value if value of current Index + A[current Index] is greater than Maximum reachable index. That is,

MaxReachable = max( MaxReachable, current Index + A[current Index])

One point to reconsider is, What if after the updation of this Maximum reachable index its value is less than or equal to current Index?
Well, this the case where we can not move from this current position and hence we can never reach the end index, therefore, in this case we simply return -1, indicating that no answer is possible in this case.

Now, we need to think about the correctness of our greedy approach again.

Can simply incrementing number of jumps when the value of current index is equal to max reachable index, always yield the correct answer everytime?

The answer would be a No, as max reachable index is getting updated and incremented by a value of A[current index] every time, this way value of current index can never be equal to max reachable index except for the case when the answer for a case isn’t possible.

For making our approach perfect, we can take another variable which keeps the track of current reachable index, and instead of incrementing the value of jump when current index is equal to Max reachable index, we will increment jump when the current Index becomes equal to current reachable, and at this moment we update the current reachable to max reachable index also.

Time Complexity Discussion :
We visit every index exactly once and keep updating the declared variables as we traverse the given array having ‘n’ elements. Therefore, the worst time complexity of this algorithm is O(n) where n is the size of the given array.

public class minJumpsArr {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] A = { 2, 3, 1, 1, 4 };

        int ans = jump(A);
        if(ans == -1)
        {
            System.out.println("Not Possible");
        }
        else {
            System.out.println("Minimum jumps required : " + ans);
        }

    }

    public static int jump(int[] a) {
        /*three variable as discussed in the editorial*/
        int maxReachable = 0;
        int jumps = 0;
        int currReachable = 0;
        /*exploring every index in the given array */
        for (int currIdx = 0; currIdx < a.length; currIdx++) {

            /*updating max reachable index every time we visit a new index*/
            maxReachable = Math.max(maxReachable, currIdx + a[currIdx]);

            /* as we have already considered the max jump length at this
             * index and if max reachable index is still equal to or
             * less than current index, then we can move forward from
             * this index therefore answer is not possible in this case*/
            if (maxReachable <= currIdx) {
                return -1;
            }

            /*if current index is equal to the current reachable, increment
             * jumps required and update current reachable*/
            if (currIdx == currReachable) {
                jumps++;
                currReachable = maxReachable;
            }
        }
        return jumps;
    }

That’s all about the Minimum Number of Jumps to reach last Index.

Longest common Subsequence

Java2blog — Sat, 02 Feb 2019 18:14:50 +0000

If you want to practice data structure and algorithm programs, you can go through Java coding interview questions.

Given two Strings A and B. Find the length of the Longest Common Subsequence (LCS) of the given Strings.
Subsequence can contain any number of characters of a string including zero or all (subsequence containing zero characters is called as empty subsequence). Characters need not to be contiguous but must maintain the relative order as in the given String. We need to find the maximum length of this subsequence which has characters common to both the given Strings.

INPUT :
A : JAVABLOG
B : ABLGOUTPUT :
4

APPROACH – I (RECURSIVE):

We just need to find the maximum length of a sequence containing characters common to both the strings in the relative order same as that of the given Strings.
In this approach we calculate our result in bottom-up manner that is, while returning from recursion.
We keep on shortening the length of the given Strings by one character, and once we hit the basecase, this is the point where at least one of the two string is exhausted having size zero. So in this case we can not have any matching character in the two strings, therefore, we return 0.
As we know we kept on removing the first character of the string in every recursion state, now the result of the bigger string will depend on the result of these smaller Strings.
Now to find this, two possibilities arise :

Case 1 :

When the two characters match.

If the both the character matches then we can add 1 to the length of the LCS found till now and can return one plus the result of shortened strings which we will get from recursion.
that is, 1 + LCS( shortened A, shortened B)

Case 2 :

When the two characters do not match.
If the characters do not match, then there are chances are, that the first character of String A matches with some other character in B or the first character of B matches with some other character in A. But as we need our result to be maximum therefore we return the maximum of these two calls.
that is, Maximum of (LCS of shortened A & B) and (LCA of A and shortened B).

As at every point we are making two calls when the first character of the two strings does not match, therefore, in the worst case where there is no matching characters in either of the two strings, then in that case our worst time complexity will be O(2^n), where n is the length of the shorter String.

Consider an Example for better understanding and its recursion tree,
A : son
B : nop

As we can see, in the recursion tree, we make only one call for remaining Strings whenever the first character matches and in every other case we make two calls.
At every base case condition we are returning zero and we are returning one plus the result achieved from recursion whenever there is a match in the first two characters.

package DynamicProgramming;

import java.util.Scanner;

public class LongestCommonSubs {

    public static void main(String[] args) {

        Scanner scn = new Scanner(System.in);

        String A = scn.nextLine();
        String B = scn.nextLine();

        System.out.println(LCS(A, B));

    }

    public static int LCS(String A, String B)
    {
        /*if one String is exhausted or is empty then 
         * there can not be any matching characters in 
         * string A and B*/
        if(A.length()==0||B.length()==0)
        {
            return 0;
        }
        /*As on this state of recursion we are working
         * on first characters of strings, in next recursion
         *  we need to recur for remaining strings with first 
         *  characters removed */
        String remA = A.substring(1);
        String remB = B.substring(1);
        /* if the current first characters of both strings
         * matches then we add 1 to the LCS length and then
         * recur to find answer for remaining Strings*/
        if(A.charAt(0)==B.charAt(0))
        {
            int remRes = LCS(remA, remB);
            return 1 + remRes;
        }
        else {
            /*if the current first characters of both strings 
             * does not match, then maximum length of LCS of 
             * current string will be the max LCS of 
             * (remaining A and B) or (A and remaining B) */
            int remRes = Math.max(LCS(remA, B), LCS(A, remB));
            return remRes;
        }
    }

}

Approach – II : Dynamic Programming:

We can clearly see the duplication of the calls represented by red colour in the recursion tree where result of same problem is getting calculated again. These Overlapping Subproblems are leading to an increase in Time Complexity of this algorithm.
Also, The result of bigger problem can be calculated with the help of results of smaller subproblems as we discussed in the recursive approach how we calculated the maximum length of LCS of a bigger string with the help of results of the smaller (shortened) strings.
As this problem has both the properties of Dynamic Programming, that is, Overlapping subproblems and Optimal Substructure. Therefore, we can use an approach involving dynamic programming to efficiently solve this problem.

We keep a Two – Dimensional matrix DP[][] of length (N+1) x (M+1) where N and M are the lengths of two given Strings A and B. Any cell DP[i][j] will represent the maximum length of LCS of two substrings, that is, A[1...i] & B[1...j], where A and B are the two given Strings.

Base cases would be the problems whose solution is known without any further computation. In this approach,
DP[0][j] = 0 and DP[i][j] = 0 wherein both the cases atleast one string has length zero and in that case LCS would obviously be zero. Also to store this base case result, Length of DP matrix is one plus the length of given Strings.

The final result of this problem will be on the cell DP[N][M] as this cell represents the LCS of
strings A[1...N] & B[1...M], where A and B are the two given Strings and N & M are their lengths respectively.

Discussion of Optimal Substructure :

CASE-1 :

We know, if the first character of the current strings/ substrings matches then we make call for the shortened strings and add one to the LCS being calculated as the current characters match.
Similarly here in this DP approach, if A[i] = B[j] that is, character at ith position in A matches with character at jth position in B, then,

DP[i][j] = 1 + DP[i-1][j-1]

DP[i-1][j-1] is cell where the result of shortened string lies, that is, A[1…i-1] and B[1…j-1]

Case-2:

if the first character of the current strings/ substrings does not match then we made two separate calls in recursive approach and final length of LCS is the result of Maximum of those two calls.
Similarly, in this DP approach if A[i] != B[j] then,

DP[i][j] = max (DP[i-1][j] , DP[i][j-1])

where,
DP[i-1][j] contains the maximum Length of LCS of A[1...i-1] and B[1...j] and,
DP[i][j-1] contains the maximum Length of LCS of A[1...i] and B[1...j-1].

Discussion of time complexity :

As we use a Matrix of size N X M where N and M are the lengths of the given two strings, and as we progress we calculate result for every cell.
That is why, the Worst time complexity of this approach for solving this problem would be O(NM).

package DynamicProgramming;

import java.util.Scanner;

public class LongestCommonSubs {

    public static void main(String[] args) {

        Scanner scn = new Scanner(System.in);

        String A = scn.nextLine();
        String B = scn.nextLine();

        System.out.println(LCS(A, B));

    }

    public static int LCS(String A, String B) {
        /* matrix for storing results of the subproblems, size is
         * one more than the string length to store the base case 
         * results*/
        int[][] dp = new int[A.length() + 1][B.length() + 1];
        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[0].length; j++) {
                /*checking characters at index - 1 as 0th character
                 *  of given String is at 1st index in DP matrix */
                if (A.charAt(i-1) == B.charAt(j-1)) {
                    /*optimal substructure as explained in the article*/
                    dp[i][j] = 1 + dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[A.length()][B.length()];
    }

}

That’s all about Longest common Subsequence in java.

Coin Change Problem in java

Ayush Kumar — Fri, 07 Dec 2018 18:58:29 +0000

If you want to practice data structure and algorithm programs, you can go through Java coding interview questions.

In this post, we will see about Coin Change problem in java.

Problem

Given an Amount to be paid and the currencies to pay with. There is infinite supply of every currency using combination of which, the given amount is to be paid.
Print the number of ways by which the amount can be paid.

INPUT:
currencies = {2,3,4}
amount = 8

OUTPUT:
2, 2, 2, 2,
2, 2, 4,
2, 3, 3,
4, 4,
Number of ways we can pay using given currencies are : 4

Since we are talking about combinations, therefore, order of payments does not matter, that is, [2, 3, 3], [3, 2, 3], [3, 3, 2] all the ways involving same frequency of currencies will be considered as one way.

Solution

Recursive Approach:

In this approach, we will make a recursive call subtracting all the currencies one by one in a loop, that is,

we will subtract the currency on the current index from the amount to be paid and make the recursive call for the remaining amount to be paid.
We keep a string which keeps track of all the payments made so far, and whenever any call is made, we just concatenate the paid currency in the string.
Once we reach to a point where the amount to be paid is zero, this becomes our basecase and we print the payments made so far string and return one as this is one way we can pay the required amount.
If the amount left to be paid become negative, this means that we do not have a perfect combination of coins perfectly adding upto the amount to be paid, therefore it is not a way to pay, hence we return zero from this type of basecase.
While we make call, we need to make sure that we do not make a payment with a currency having index lower than the current index, as this will lead to the duplications in the combination which we do not want. Therefore, whenever we make calls in loop we initialise our loop variable with the current currency index not from 0th index.
As at every stage of the amount to be paid, we are making {number of currencies – current index} number of calls, Say n.
And the initial amount to be paid = x,
then the worst time complexity of this algorithm is x^n.

package DynamicProgramming;

import java.util.Scanner;

public class CoinChange {

    public static void main(String[] args) {

        Scanner scn = new Scanner(System.in);
        int[] currencies = new int[scn.nextInt()];

        for (int i = 0; i < currencies.length; i++) {
            currencies[i] = scn.nextInt();
        }

        int amount = scn.nextInt();

        System.out.println(
        "Number of ways we can pay using given currencies are : " + 
                             coinchange(0, amount, currencies, ""));

    }

    public static int coinchange(int ci, int remaining, int[] currencies,
                                   String paid) {
        if (remaining == 0) {
            /*
             * this means the amount to be paid can be paid
             *  using only the given currencies.
             */
            System.out.println(paid);
            /*
             * as this is one of the way to pay, hence it 
             * will contribute +1 number of ways for itself
             */
            return 1;
        }
        if (remaining < 0) {
            /*
             * if the remaining amount to be paid is negative,
             * this means that the set of coins we've paid does 
             * not add upto the amount to be paid, hence it is 
             * not one of the way to pay.
             */
            return 0;
        }

        int res = 0;
        for (int i = ci; i < currencies.length; i++) {

            /*
             * we must start our loop from current index, as 
             * if we loop through all currencies once again 
             * then there will be a repetition in the ways used 
             * to pay the amount.
             */
            res += coinchange(i, remaining - currencies[i], currencies, 
                    paid + Integer.toString(currencies[i]) + ", ");

        }

        return res;

    }

}

Consider the following recursion tree for testcase : Amount = 8, Currencies = [2,4]

EFFICIENT APPROACH:

Consider the recursion tree above,

We can clearly see duplication of calls, where result of amount = 4 and amount = 2 are being calculated again and again that is, there is an overlap in most of the subproblems which is increasing the complexity of the algorithm.
Also, we can see the result for bigger subproblem is being calculated in post order, that is, after we get the result for the smaller subproblems, the result for bigger subproblem is addition of all its child that is, smaller subproblems.
As this problem has both the properties of Dynamic Programming, which are Overlapping subproblems and Optimal Substructure. Therefore, we will adopt a Dynamic Programming approach to reduce the worst time complexity of the solution.

Algorithm:

We make an Array to store the result of smaller subproblems, say dp, of size amount + 1,
because at ith index we store the number of ways to pay an amount = i, so for the having an index ‘amount’ we need to make an array of amount + 1 size.
We basically process this array for every currency, that is, for every currency we run a loop over the dp array to calculate the total number of ways to pay the amount with number of currencies = current currency index + 1.
The point to understand for understanding this algorithm is that,
if current amount – current currency can be paid using this currency then, current amount can also be paid, that is, if (dp[amt – currency]) >= 1 then (dp[amt]++)
So for every currency at every amount we just need to check if the amount-currency is greater than one that is, if it can be paid. If no, then this amount also cant be paid with the current set of currencies.
Now as for every currency we are processing every amount ranging from 0 to given amount,
Hence the worst time complexity of this approach would be O(amount * num_currencies)

package DynamicProgramming;

import java.util.ArrayList;
import java.util.Scanner;

public class CoinChange {

    public static void main(String[] args) {

        Scanner scn = new Scanner(System.in);
        int[] currencies = new int[scn.nextInt()];

        for (int i = 0; i < currencies.length; i++) {
            currencies[i] = scn.nextInt();
        }

        int amount = scn.nextInt();

        coinchangeDP(amount, currencies);

    }

    public static void coinchangeDP(int amount, int[] currencies) {
        /*
         * dp array will contain the number of ways 'i'
         * amount can be paid using the given currencies,
         * therefore, we made dp of size amount+1 to have
         * an index = amount.
         */
        int[] dp = new int[amount + 1];
        ArrayList[] payments = new ArrayList[amount+1];
        for(int i=0;i();
        }

        /*
         * positive basecase, when we have remaining amount = 0, 
         * this means that we have found one way of paying the 
         * initial amount.
         */
        dp[0] = 1;

        for (int currency : currencies) {
        for (int amt = 1; amt < dp.length; amt++) {
        if(amt-currency >=0 && dp[amt - currency] != 0)
        {
        dp[amt] +=1;
            /*  we have made an array of arraylist of strings to
         * store all the ways of paying the current amount,
             *  therefore, the payments of current amount = 
         *  payments of (amt - currency) concatenated 
         *  with the current currency*/
        payments[amt].add(payments[amt-currency].size()>0? 
      (payments[amt-currency].get(payments[amt-currency].size()-1) + currency + " ") 
       : Integer.toString(currency) + " ");
                }
            }
        }

        /*number of ways of paying given amount = dp[amount]*/
        System.out.println(dp[amount] + "\n" + payments[amount]);

    }

}

That’s all about Coin change problem in java.

Edit Distance Problem

Ayush Kumar — Tue, 30 Oct 2018 18:47:55 +0000

If you want to practice data structure and algorithm programs, you can go through Java coding interview questions.

In this post, we will see edit distance problem in java. Sometimes this problem also referred as "String distance replacement in java"

Problem

Given two strings string1 and string2, String1 is to be converted into String2 with the given operations available in the minimum number of steps. Using any one of the given operations contributes to the increment of steps by one.

Allowed Operations are :
(i) Remove : This operation allows the Removal any one character from String.
(ii) Insert : This operation allows the Insertion of one character at any spot in the String.
(iii) Replace : This operation allows the replacement of any one character in the string with
any other character.

Input:

bacbbd
cabddb

Output: 4

Solution

Naive Approach :

We will process the strings from start, and move towards the end solving the problem for the current character.

If the current character of the strings match, we don’t do any operation to make them equal and we recur for the remaining Strings.
If the current character of the strings does not match, we make three calls for the three operations, add one to the total number of operations took to make the Strings equal and recur for remaining subproblem depending on the type of operation, i.e.
For explaining let us define remaining String as the substring of the actual string which does not include the first character i.e remaining string = substring(1, string.length).
(i) for removal : we recur for remaining_String1 and String2.
(ii) for insertion : we recur for String1 and remaining_String2.
(iii) for replacement : we recur for remaining_String1 and remaining_String2.

As at every point we are making 3 calls when character is different, and one call when character matches, Considering the worst case, let’s assume that no character in either string matches, then at every character we need to make 3 calls.
let’s define ‘n’ as the minimum(string1.length(), string2.length()).
therefore, the worst time complexity of the algorithm would be O(3^n).

import java.util.Scanner;

public class EditDistance {

    public static void main(String[] args) {

        Scanner scn = new Scanner(System.in);

        String s1 = scn.nextLine();
        String s2 = scn.nextLine();

        System.out.println(editDistRecusrsive(s1, s2));

    }

    public static int editDistRecusrsive(String s1, String s2) {
        /*
         * basecase : if one String is exhausted, return the remaining 
         * length of the other String, as we have to do atleast that 
         * many opeartions to make the Strings equal.
         */
        if (s1.length() == 0) {
            return s2.length();
        }

        if (s2.length() == 0) {
            return s1.length();
        }

        /*
         * we are working on the first characters of both 
         * strings and recurring for the remaining length 
         * of the strings.
         */

        String remaining1 = s1.substring(1);
        String remaining2 = s2.substring(1);
        int recRes = 0;

        if (s1.charAt(0) == s2.charAt(0)) {
            /* if characters match we dont need to do any 
             * operations to make them equal, so leave them 
             * and recur for the remaining strings
             */
            recRes = editDistRecusrsive(remaining1, remaining1);
        } else {

            /*
             * if the first characters dont match, then we add +1 
             * for the operation used in making the first characters 
             * of the strings equal, and recur for the remaining Strings
             * and our final answer will be 1 + minimum of the operations 
             * taken to convert remaining String! and remaining String2.
             */
            recRes = 1 + Math.min(editDistRecusrsive(remaining1, remaining2),
                 Math.min(editDistRecusrsive(remaining1, s2), 
                                 editDistRecusrsive(s1, remaining2)));

        }

        return recRes;
    }

EFFICIENT APPROACH :
We can definitely see overlapping subproblems in the recursive solution where the result for the same problem is being calculated again and again which increases the complexity to such a higher extent. Also the result for the bigger problem is being calculated using the optimal result of its smaller subproblems which we can see in the code of our previous algorithm. As this algorithm follow both the required properties of Dynamic programming, that is, Optimal substructure and Overlapping Subproblems, hence, this problem points to the use of Dynamic programming to reduce the complexity of the algorithm, where the result for a duplicate call will not be calculated again and again.

Algorithm:

We make a 2D DP array for storing our result for the subproblems.
Lets name it DP and its size will be (string1.length + 1)*(string2.length + 1)
Any cell(i, j) will contain the result for the the number of operations needed to make the two strings (String1.substring(i, string1.length()))&(String2.substring(j, string2.length())) matching.
The last Row of the matrix will contain the result of : (String1.substring(current column, string1.length) & empty string2
The last column of the matrix will contain the result of : empty string1 & (String1.substring(current column, string1.length))

The last two points actually are the base cases of our problem and we move backward to calculate the result of the bigger subproblem,

How?

Suppose we are calculating the result of a cell, DP[row][col]

Now if the character of String1 at current column matches the character of String2 at current row, DP[row][col] = DP[row + 1][col + 1]
This is basically equivalent to the call for the result of (remaining_String1, remaining String2), as the current character matches, so we dont need to do any operations for making them equal.
What if the character of String1 at current column does not matches the character of String2 at current row,
then the result for the current cell will be, DP[row][col] = min of(DP[row + 1][col], DP[row][col+1], DP[row + 1][col + 1])which is equivalent to Minimum of call for all three operations, that is,

(i) for removal : DP[row][col + 1], that is, remaining_String1 and String2
(ii) for insertion : DP[row + 1][col], that is, String1 and remaining_String2
(iii) for replacement : DP[row+1][col+1], that is, remaining_String1 and remaining_String2.

Eventually the result i.e. the minimum number of operations required for making both the strings matching is at the cell, DP[0][0] which represents the result of both COMPLETE strings.

package org.arpit.java2blog;

import java.util.Scanner;

public class EditDistance {

    public static void main(String[] args) {

        Scanner scn = new Scanner(System.in);

        String s1 = scn.nextLine();
        String s2 = scn.nextLine();

        System.out.println(editDist(s1, s2));

    }

    public static int editDist(String s1, String s2) {
        int[][] dp = new int[s1.length() + 1][s2.length() + 1];

        /* this is the last column of the matrix which 
         *  represents the result of empty string1
         *  and string2 starting from current row.
         */
        for (int row = s2.length(); row >= 0; row--) {
            dp[row][s1.length()] = s2.length() - row;
        }

        /* this is the last row of the matrix which
        * represents the result of empty string2
        *  and string1 starting from current col.
        */
        for (int col = s1.length(); col >= 0; col--) {
            dp[s2.length()][col] = s1.length() - col;
        }

        for (int col = s1.length() - 1; col >= 0; col--) {
            for (int row = s2.length() - 1; row >= 0; row--) {

                /* If characters are same, then the solution will be without 
                 * these characters */
                if (s1.charAt(col) == s2.charAt(row)) {
                    dp[row][col] = dp[row + 1][col + 1];
                } else {
                /* else it will be minimum of these three operations
                */
                dp[row][col] = 1 + Math.min(dp[row + 1][col + 1], // replace
                                Math.min(dp[row][col + 1]  //   removal
                                , dp[row + 1][col]));   // insertion
                }
            }
        }

        return dp[0][0];
    }
}

That’s all about Edit Distance Problem in java or String distance replacement in java.

Longest common substring

Java2blog — Sun, 30 Sep 2018 17:58:50 +0000

If you want to practice data structure and algorithm programs, you can go through 100+ data structure and algorithm programs.

In this post, we will see how to find the longest common substring in java.

Program

Given two String, find longest common substring.
For example:

String 1: Java2blog
String 2: CoreJavaTutorial
Longest common subString is: Java

Solution

Brute force approach

You can solve this problem brute force. Let’s say you are given two String str1 and st2. Length of Str1 be m and length of str2 be n.You can find all substrings of str1 in o(m^2) time then search each of substring in str2, so total complexicity of algorithm will be o(m^2*n).

Dynamic programming solution

You can solve this problem with the help of dynamic programming.Here is simple algorithm.

Initialize 2D array of m*n named “dp”
Iterate over str1 in outer loop(Using i)
Iterate over str2 in inner loop(Using j)
If str.charAt(i) == str2.charAt(j)
- If i or j=0 then put dp[i][j] = 1
- If i !=0 and j!=0
  - dp[i][j] = dp[i-1][j-1] + 1
Keep the track of max and endIndex in process
Find substring with the help of endIndex and max.

Here max denotes the size of longest common substring.

Here is simple program to find longest common sustring in java.

package org.arpit.java2blog;
	
	public class LongestCommonSubstringMain {
	
		public static void main(String[] args) {
			String str1="Java2blog";
			String str2="CoreJavaTutorial";
			LongestCommonSubstringMain lcsMain=new LongestCommonSubstringMain();
			System.out.println("String 1: "+str1);
			System.out.println("String 2: "+str2);
			System.out.println("Longest common subString is: " +lcsMain.getLongestCommonSubstring(str1, str2));
	
		}
		public String getLongestCommonSubstring(String str1, String str2){
			int m = str1.length();
			int n = str2.length();
	
			int max = 0;
	
			int[][] dp = new int[m][n];
			int endIndex=-1;
			for(int i=0; i
When you run above program, you will get below output:
String 1: Java2blog

String 2: CoreJavaTutorial

Longest common subString is: Java
The time complexity of this algorithm is o(m*n)

That ‘s all about Longest common substring in java.

Count all paths from top left to bottom right of MxN matrix

Java2blog — Mon, 13 Aug 2018 05:44:26 +0000

If you want to practice data structure and algorithm programs, you can go through Java coding interview questions.

In this post, we will see about how to count all paths from top left to bottom right of MxN matrix.

Problem

We need to count all paths from top left to bottom right of MxN matrix. You can either move down or right.

Solution

You can solve this problem using recursion.

Recursion

public int countMatrixPathsRec(int [][] matrix, int row, int col){
        //base case
        // If you reach at last row or column then you have only one path to go
        if(row==matrix.length-1 || col==matrix[0].length-1){
            return 1;
        }
        return countMatrixPathsRec(matrix, row+1, col) + countMatrixPathsRec(matrix, row, col+1);
    }

Recursion will work fine but time complexity of this solution will be exponential as there are lots of overlapping subproblems here.

We can use dynamic programming to solve the problem. We won’t recompute any subproblem more than once.

Dynamic programming

Here is simple algorithm for dynamic programming solution.

Initialize an array dp with matrix’s dimensions. This array will give us final count, once we reach to bottom right.
Fill the first row with 1, as you can reach here from one direction(by going right)
Fill the first column with 1 as well, as you can reach here from one direction(by going down).
Iterate over all other rows and columns and use formula dp=dp[i-1][j] + dp[i][j-1], as you can reach here from two directions (By going right or By going down)
return dp[matrix.length-1][matrix[0].length-1]

Here is a diagramtic illustration of the algorithm.

public int countMatrixPathsDynamicProgramming(int [][] matrix){
        int dp [][] = new int[matrix.length][matrix[0].length];

        // no of path for first row will be 1 as you can move only in one direction
        for (int i = 0; i 
Here is complete program to Count all paths from top left to bottom right of MxN matrix.
package org.arpit.java2blog;

public class CountMatrixPaths {

    public static void main(String[] args)
    {
        CountMatrixPaths cmp=new CountMatrixPaths();
        int[][] matrix= {
                {1,2,3},
                {4,5,6},
                {7,8,9}
        };

        int totalPathsRec = cmp.countMatrixPathsRec(matrix,0,0);
        System.out.println("Total paths to reach top left to bottom right using recursion: "+totalPathsRec);

        int totalPaths = cmp.countMatrixPathsDynamicProgramming(matrix);
        System.out.println("Total paths to reach top left to bottom right using DP: "+totalPaths);

    }

    public int countMatrixPathsRec(int [][] matrix, int row, int col){
        //base case
        // If you reach at last row or column then you have only one path to go
        if(row==matrix.length-1 || col==matrix[0].length-1){
            return 1;
        }
        return countMatrixPathsRec(matrix, row+1, col) + countMatrixPathsRec(matrix, row, col+1);
    }

    public int countMatrixPathsDynamicProgramming(int [][] matrix){
        int dp [][] = new int[matrix.length][matrix[0].length];

        // no of path for first row will be 1 as you can move only in one direction
        for (int i = 0; i 
Here is output of the above program.
Total paths to reach top left to bottom right using recursion: 6

Total paths to reach top left to bottom right using DP: 6
That’s all about counting all paths from top left to bottom right of MxN matrix.

Memoization example in java

Java2blog — Sat, 11 Aug 2018 18:56:41 +0000

If you want to practice data structure and algorithm programs, you can go through Java coding interview questions.

In this tutorial, we will see about Memoization example in java.

Let me start with the question.

Would you like to do same task again and again when you know that it is going to give you same result? I think Answer will be No.

So Memoization ensures that method does not execute more than once for same inputs by storing the results in the data structure(Usually Hashtable or HashMap or Array).
Let’s understand with the help of Fibonacci example.
Here is sample fibonacci series.

0,1,1,2,3,5,8,13,21,34,55,89,144..

So it has recurrence relation of:

F(n)= F(n-1)+F(n-2)

So Let’s write recurrence function for it.

// Fibonacci without Memoization
    public int fibonacci(int n){

        if( n == 0 ) return 0;
        if( n == 1 ) return 1;

        System.out.println("Calculating fibonacci number for: "+n);
        return (fibonacci(n-1) + fibonacci(n-2));   
    }

When you run above code with n=5, you will get below output.

Calculating fibonacci number for: 5
Calculating fibonacci number for: 4
Calculating fibonacci number for: 3
Calculating fibonacci number for: 2
Calculating fibonacci number for: 2
Calculating fibonacci number for: 3
Calculating fibonacci number for: 2
Fibonacci value for n=5: 5

As you can see, we are calculating fibonacci number for 2 and 3 more than once.

Let’s draw a recursive tree for fibonacci series with n=5.
Here two children of node will represent recursive call it makes.

If you notice here, we are calculating f(3) twice and f(2) thrice here, we can avoid duplication with the helping of caching the results.
We will use one instance variable memoizeTable for caching the result.

Check if n is already present in memoizeTable, if yes, return the value
If n is not present in memoizeTable, then compute and put the result in memoizeTable.

package org.arpit.java2blog;

import java.util.HashMap;
import java.util.Map;

public class FibonacciMemoizationAlgorithm {

    private Map memoizeTable = new HashMap<>(); // O(1)

    // Fibonacci with Memoization
    public int fibonacciMemoize(int n){

        if( n == 0 ) return 0;
        if( n == 1 ) return 1;

        if( this.memoizeTable.containsKey(n) ) 
        {
            System.out.println("Getting value from computed result for "+n);
            return this.memoizeTable.get(n);
        }

        int result = fibonacciMemoize(n-1)+ fibonacciMemoize(n-2);

        System.out.println("Putting result in cache for "+n);
        this.memoizeTable.put(n, result);

        return result;

    }

    // Fibonacci without Memoization
    public int fibonacci(int n){

        if( n == 0 ) return 0;
        if( n == 1 ) return 1;

        System.out.println("Calculating fibonacci number for: "+n);
        return (fibonacci(n-1) + fibonacci(n-2));   
    }

    public static void main(String[] args) {

        FibonacciMemoizationAlgorithm fibonacciAlgorithm = new FibonacciMemoizationAlgorithm();
        System.out.println("Fibonacci value for n=5:  "+fibonacciAlgorithm.fibonacciMemoize(5));

    }
}

When you run above program, you will get below output.

Putting result in cache for 2
Putting result in cache for 3
Getting value from computed result for 2
Putting result in cache for 4
Getting value from computed result for 3
Putting result in cache for 5
Fibonacci value for n=5: 5

As you can see, we are not computing fibonacci number for 2 and 3 more than once.
That’s all about Memoization in java.