Java Programs›Strings›Find Longest Palindromic Substring

Find Longest Palindromic Substring in Java

advanced· Strings · String

Problem

A palindromic substring is a contiguous run of characters that reads the same forwards and backwards — the longest one is the biggest such run anywhere inside the string.

Given a string, find its longest substring that is a palindrome.

Input

cabbad

Output

Longest palindromic substring: abba

Java Program

Java

public class LongestPalindromicSubstring {
    static String expand(String str, int left, int right) {
        while (left >= 0 && right < str.length() && str.charAt(left) == str.charAt(right)) { // grow outward while both bounds stay valid and the characters match
            left--;
            right++;
        }
        return str.substring(left + 1, right);
    }

    public static void main(String[] args) {
        String str = "cabbad";
        String longest = "";

        for (int i = 0; i < str.length(); i++) {
            String odd = expand(str, i, i);       // centered on one character
            String even = expand(str, i, i + 1);  // centered on the gap between two characters
            if (odd.length() > longest.length()) longest = odd;
            if (even.length() > longest.length()) longest = even;
        }

        System.out.println("Longest palindromic substring: " + longest);
    }
}

▶ Run Code

Output

Longest palindromic substring: abba

Core Logic

Every palindrome has a center — treating each character, and each gap between characters, as a possible center and expanding outward while the ends match finds every palindrome in the string.

How It Works

1expand(str, left, right) grows outward from a center, moving left back and right forward as long as the characters at those positions match.
2For each index i, expand(str, i, i) checks the odd-length palindrome centered on that single character.
3expand(str, i, i + 1) checks the even-length palindrome centered on the gap between i and i + 1.
4Whichever expansion produces a longer result than the current longest replaces it.

For "cabbad", expanding from the gap between the two middle 'b's grows outward to "abba", the longest palindrome found across every center tried.

💡

Key Point: Both odd-length centers (a single character) and even-length centers (a gap between two characters) have to be checked — a palindrome like "abba" only has an even-length center, with no single middle character.

Complexity

Time Complexity: O(n²)Space Complexity: O(n)

Why: Each of the n possible centers can expand outward up to O(n) times, so the total time is O(n²), while only the current best substring needs to be kept in memory.

Key Concepts

expand around centerodd and even length palindromesrunning maximum

Approach 2: Dynamic Programming

Java

public class LongestPalindromicSubstringDP {
    public static void main(String[] args) {
        String str = "cabbad";
        int n = str.length();
        boolean[][] dp = new boolean[n][n];
        int start = 0, maxLength = 1;

        for (int i = 0; i < n; i++) dp[i][i] = true; // every single character is a palindrome

        for (int len = 2; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                if (str.charAt(i) == str.charAt(j)) {
                    dp[i][j] = (len == 2) || dp[i + 1][j - 1]; // true if the ends match and the inner substring is already a palindrome
                    if (dp[i][j] && len > maxLength) {
                        start = i;
                        maxLength = len;
                    }
                }
            }
        }

        System.out.println("Longest palindromic substring: " + str.substring(start, start + maxLength));
    }
}

▶ Run Code

Output

Longest palindromic substring: abba

Core Logic

A substring is a palindrome exactly when its two ends match and everything between them is also a palindrome — building a table of that fact bottom-up avoids re-checking the same inner substrings repeatedly.

How It Works

1dp[i][j] is true when the substring from index i to j is a palindrome; every single character starts out true on its own.
2For each substring length from 2 up to n, the code checks whether the characters at both ends match and the substring inside them (dp[i + 1][j - 1]) is already known to be a palindrome.
3A length-2 substring is a palindrome as soon as its two characters match, since there's nothing between them to check.
4Whenever a longer palindrome is confirmed, its starting index and length are recorded.

For "cabbad", dp[1][4] ("abba") is marked true once str.charAt(1) == str.charAt(4) and the inner substring dp[2][3] ("bb") is already known to be a palindrome.

💡

Key Point: This trades the expand-around-center version's O(n) space for O(n²), in exchange for building the answer from a table of already-solved smaller subproblems instead of re-expanding from scratch at every center.

Complexity

Time Complexity: O(n²)Space Complexity: O(n²)

Why: The table holds one boolean per pair of start/end indices, so both the table's memory and the nested loop filling it scale with n².

Key Concepts

2D boolean tabletabulationsubstring length

← Previous

Find Least Frequent Character in a String

Find Longest Word in a String

Related Programs

Check Palindrome String

Stringsintermediate

Check Pangram

Stringsbeginner

Check String Contains Only Alphabets