Leetcode 5. Longest Palindromic Substring

Question

Dind the longest palindromic substring in a given string s

Solution 1 - Brute Force

Enumerate all substrings, determine whether it is a palindrome string, and save the longest palindrome string.

Time complexity: need 2 for loop to enumerate all substring O(n²), and 1 for loop to determine if a string is palindrome. Thus overall time complexity O(n³).

Solution 2 - Expand from central

We know that the palindrome string must be symmetrical, so we can select a center each time, expand left and right, and determine whether the left and right characters are equal.

Because there are strings with odd length and even length, we need to expand from one central or from two central, so there are n + n-1 central in total.

public String longestPalindrome(String s) {
    if (s.length() == 1) {
        return s;
    }

    String result = "";

    for (int i = 0; i < s.length() - 1; i++) {
        // central is 1 char
        int length = expand(s, i, i);
        // central is 2 chars
        int length2 = expand(s, i, i + 1);

        int longer = Math.max(length, length2);

        if (longer > result.length()) {
            result = s.substring(i - (longer - 1) / 2, i + longer / 2 + 1);
        }
    }

    return result;
}

// given string s, expand from given central
private int expand(String s, int start, int end) {
    int left = start;
    int right = end;

    while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
        left--;
        right++;
    }

    return right - left - 1;
}

Time complexity: O(n²)

Solution 3 - Manacher’s Algorithm

Manacher’s Algorithm is a linear algorithm used to find the longest palindrome substring of a string. It was invented by a man named Manacher in 1975. The biggest contribution of this algorithm is to decrease the time complexity to Linear.

See: Manacher’s Algorithm. I will have a separate blog takling about this algothm in the future.

Question

Similar Questions

Solution 1 - Brute Force

Solution 2 - Expand from central

Solution 3 - Manacher’s Algorithm