Alg.13 Longest Palindromic Substring

From algoexpert.io

Previous problem explains what is a palindrome string, in this problem, we will write a function to find out the longest palindromic substring within a given string.

In the solution, we consider each character as a center of a potential palindrome, however, when a string contains even number elements, the center should contains 2 characters. So, we write a function to find longest palindrome given a center.

public static int[] findLPS(String str, int left, int right) {
        while (left >= 0 && right < str.length()) {
            if (str.charAt(left) != str.charAt(right)) break;
            left--;
            right++;
        }
        
        return new int[]{left + 1, right};
}

Now, we iterate the string, find its longest palindromic substring

public static String longestPalindromicSubstring(String str) {
    int[] ans = {0, 1};
        for (int i = 1; i < str.length(); i++) {
            int[] odd = findLPS(str, i - 1, i + 1);
            int[] even = findLPS(str, i - 1, i);
            int[] longest = (odd[1] - odd[0]) > (even[1] - even[0]) ? odd : even;
            ans = (longest[1] - longest[0]) > (ans[1] - ans[0]) ? longest : ans;
        }
    return str.substring(ans[0], ans[1]);
  }

Time complexity: O(n^2); Space complexity: O(n)

Donate