CODEWITHSUNDEEP
javasubstringpalindrome
Reena Puthota
Reena Puthota

Reputation: 21

Return longest palindromic substring [Java]

Here is longest palindrome solution I have written using dynamic programming with memoization. It passes several of the test cases (46/142), but the solution is not at 100% on Leetcode. Time limit is exceeding (TLE) for very long inputs. How to make it work for long inputs as well?

public String longestPalindrome(String s) {
    Map<List<Integer>, String> memo = new HashMap<>();
    return longest(s, 0, s.length()-1, memo);
}

public static String getMaxString(String s1, String s2) {
    return (s1.length() > s2.length() ? s1 : s2);
}

public String longest(String s, int i, int j, Map<List<Integer>, String> memo) {
    // Invalid indices.
    if (i > j) {
        return "";
    }
    
    List<Integer> keyPair = List.of(i, j);
    if (i == j) {
        return s.substring(i, j+1);
    }

    // Return palindrome if already evaluated.
    if(memo.containsKey(keyPair)) {
        return memo.get(keyPair);
    }
    
    // Check if the inner string is also a palindrome and update max accordingly.
    String max = longest(s, i+1, j-1, memo);
    if ((max.length() == (j-1) - (i+1) + 1) &&
        (s.charAt(i) == s.charAt(j)))
    {
        max = s.substring(i,j+1);
    }

    // Get max of all possible palindromes within [i,j].
    max = getMaxString(max, getMaxString(longest(s, i+1, j, memo),
                                         longest(s, i, j-1, memo)));

    memo.put(keyPair, max);
    return memo.get(keyPair);
}

I have seen various other algorithms for this problem, but, what I am specifically looking for is to understand how to make my solution work for all inputs (or) the gaps in my solution.

Upvotes: -5

Views: 104

Answers (1)

Unmitigated
Unmitigated

Reputation: 89314

First, your solution is O(N^3): you have O(N^2) states (the possible pairs of indexes corresponding to substrings) and you potentially call substring in each recursive call, which is O(N).

Instead of returning the actual string from the recursive longest method, simply return a pair of integers to represent the substring. This representation allows constant time manipulation and reduces the overall time complexity to O(N^2); you only need to call substring to get the result at the very end.

Furthermore, while HashMap provides constant time operations on average, it has a high constant factor and can still get quite slow with a large number of keys. In this case, you already know the possible key values (indexes are all between 0 and s.length() - 1), so it is more efficient to use a 2d array to store the memoized results.

public String longestPalindrome(String s) {
    var memo = new int[s.length()][s.length()][];
    var ret = longest(s, 0, s.length()-1, memo);
    return s.substring(ret[0], ret[1]);
}

public static int[] getMaxString(int[] s1, int[] s2) {
    return s1[1] - s1[0] > s2[1] - s2[0] ? s1 : s2;
}

public int[] longest(String s, int i, int j, int[][][] memo) {
    if (i > j) {
        return new int[2];
    }
    if (i == j) {
        return new int[]{i, j+1};
    }
    if (memo[i][j] != null) return memo[i][j];
    var max = longest(s, i+1, j-1, memo);
    if ((max[1] - max[0] == (j-1) - (i+1) + 1) &&
        (s.charAt(i) == s.charAt(j))) {
        max = new int[]{i, j+1};
    }
    max = getMaxString(max, getMaxString(longest(s, i+1, j, memo),
                                         longest(s, i, j-1, memo)));
    return memo[i][j] = max;
}

There is also a linear time solution to the longest palindromic substring problem: Manacher's Algorithm.

Upvotes: 3

Related Questions