-1

I am getting "java.lang.OutOfMemoryError: Java heap space" i have read about it and found out running Java with the command-line option -Xmx can solve this. But unfortunately i can't do that because this is an online judge problem. Can you guys suggest me any other way to reduce the heap size in the code? 

public static void main(String[] args) throws IOException {

    // Scanner bf = new Scanner(System.in);
    BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    String x = "a";
    String y = "a";

    for (int i = 0; i < 48000; i++) {
        x = x.concat("a");
        y = y.concat("a");

    }

    if (!x.isEmpty() && !y.isEmpty() && x.matches("\\p{L}+") && y.matches("\\p{L}+") && x.length() <= 50000 && y.length() <= 50000) {
        int i, j;
        int lenx = x.length();
        int leny = y.length();
        System.out.println(x.length() + " " + y.length());
        int[][] table = new int[lenx + 1][leny + 1];

    // Initialize table that will store LCS's of all prefix strings.
        // This initialization is for all empty string cases.
        for (i = 0; i <= lenx; i++) {
            table[i][0] = 0;
        }
        for (i = 0; i <= leny; i++) {
            table[0][i] = 0;
        }

    // Fill in each LCS value in order from top row to bottom row,
        // moving left to right.
        for (i = 1; i <= lenx; i++) {
            for (j = 1; j <= leny; j++) {

                // If last characters of prefixes match, add one to former value.
                if (x.charAt(i - 1) == y.charAt(j - 1)) {
                    table[i][j] = 1 + table[i - 1][j - 1];
                } // Otherwise, take the maximum of the two adjacent cases.
                else {
                    table[i][j] = Math.max(table[i][j - 1], table[i - 1][j]);
                }

            }

        }

        // This is our answer.
        System.out.println(table[lenx][leny]);
    }

    bf.close();

}

String x and y can not be more than 50000 in length.

edit: I have heard that sparse matrix uses less memory would you suggest me to implement it? increase heap is not an option because it is too large (50000X50000)

Martijn Pieters
  • 1,048,767
  • 296
  • 4,058
  • 3,343
Nitin Jaiman
  • 173
  • 1
  • 12
  • possible duplicate of [What is an OutOfMemoryError and how do I debug and fix it](http://stackoverflow.com/questions/24510188/what-is-an-outofmemoryerror-and-how-do-i-debug-and-fix-it) – Raedwald Jan 22 '15 at 00:27

1 Answers1

0

Change the datatype of variable x and y to StringBuilder as you are performing many concatination operation on these variables which are of string type.So for each concat operation a new string object is created which is causing OutOfMemory error as String are immutable.

Sachin Janani
  • 1,310
  • 1
  • 17
  • 33