Java string out of bound exception while accessing the array element

Question

public class App {

    public static int min(int x, int y)
    {
        if(x<y)
            return x;
        else
            return y;
    }

    public static int minPalPartition(String str)
    {
        int n = str.length();
        boolean P[][] = new boolean[n][n];
        int DP[][] = new int[n][n];

        //for all the string with start index and end index is same that is length is 1, string is palindrome and cut needed is 0
        for(int i=0; i<n; i++)
        {
            P[i][i] = true;
            DP[i][i] = 0;
        }

        /*
         * i start index
         * j end index
         * k intermediate index
         * l length
         */
        int i, j, k, l;

        for(l=2; l<=n; l++)
        {
            for(i=0; i<n-1; i++) //as starting index start at 0 it can go till n-2, n=3, i =0, j=1 and i=1, j=2 is the combination
            {
                j=i+l-1;

                /* first determine P[i][j], if P[i][j] is true then DP[i][j] is 0
                 * if only 2 letter just check first and last letter
                 * otherwise last 2 letter and previous result
                 */
                if(l==2)
                {
                    P[i][j]  = (str.charAt(i) == str.charAt(j));

                }
                else
                {

                    P[i][j] = (str.charAt(i)== str.charAt(j)) && P[i+1][j-1];

                }

                if(P[i][j] == true)
                {
                    DP[i][j] = 0;
                }
                else
                {
                    DP[i][j] = Integer.MAX_VALUE;
                    for(k=i; k<j; k++)
                    {
                        DP[i][j] = min(DP[i][j], (DP[i][k] + DP[k+1][j] + 1));
                    }
                }
            }
        }

        return DP[0][n-1];
    }

    public static void main(String[] args) {
        String str = "ababbbabbababa";
        System.out.println("length of the string " + str.length());
        System.out.println("pal partition Need for [" + str + "] : " + minPalPartition(str));

    }

}

In the code above I got below exception

Exception in thread "main" java.lang.StringIndexOutOfBoundsException: String index out of range: 14
    at java.lang.String.charAt(String.java:658)
    at Client.App.minPalPartition(App.java:54)
    at Client.App.main(App.java:79)

Basically it gives exception at this line

P[i][j] = (str.charAt(i)== str.charAt(j)) && P[i+1][j-1];

What is the problem? How to avoid.

This is palindrome partitioning of a string problem.

Answer 1

    j=i+l-1;
   //l=[2,n]
   //i=[0,n-2]
when l=3 i=n-2,j=n,then out of bounds

Answer 2

As others already mentioned in the comment that you have problem in the following lines of code.

for (l = 2; l <= n; l++){
    for (i = 0; i < n - 1; i++){
        j = i + l - 1;
        // rest of your code
    }
}

So, your coding is raising exception when l = 3 and i = 12, because j then becomes 12 + 3 - 1 = 14. Since your string length is 14, you cannot access index 14 and as a result getting StringIndexOutOfBoundsException exception.

From the comments you made in your code, i guess what you need is:

for (l = 2; l <= n; l++){
    for (i = 0; i < n - l; i++){
        j = i + l - 1;
        // rest of your code
    }
}

Note the condition of the inner loop, its i < n - l, not i < n - 1. So, maximum value of j can be:

j = n - l + l - 1 = n - 1

I don't what you are trying to do with your code but i have suggested this based on my guess after reading your comments in the code.