Longest Palindromic Substring

Java coding interview problem for String Coding: Longest Palindromic Substring.

The Longest Palindromic Substring is one of the most popular String interview problems asked by companies like Google, Amazon, Microsoft, Meta, Oracle, Adobe, and many others.

Although the problem looks straightforward, it evaluates several important algorithmic concepts including:

String Traversal
Two Pointers
Expand Around Center
Dynamic Programming
Manacher's Algorithm
Time Complexity Optimization

Interviewers often ask several follow-up questions such as:

Can you solve it without checking every substring?
Can you improve the brute-force solution?
What is the optimal solution?
Can you solve it in O(n) time?
What is the difference between substring and subsequence?

Learning multiple approaches prepares you for all these interview variations.

Problem Statement

Given a string s, return the longest substring that is a palindrome.

If multiple answers exist, return any one of them.

Example 1

Input

babad

Output

bab

aba

Both are correct.

Example 2

Input

cbbd

Output

bb

Example 3

Input

racecar

Output

racecar

Example 4

Input

abcd

Output

Every individual character is a palindrome.

What is a Palindrome?

A palindrome is a sequence that reads the same from both directions.

Examples

madam

racecar

level

noon

Examples that are not palindromes

java

coding

hello

What is a Longest Palindromic Substring?

A substring consists of continuous characters.

Example

babad

Possible substrings

b

ba

bab

baba

babad

Among these,

bab

is a palindrome.

Another valid answer is

aba

Why is this Question Asked in Interviews?

This problem evaluates whether candidates understand:

String Manipulation
Two Pointer Technique
Dynamic Programming
Recursion
Optimization
Time Complexity

It also introduces one of the most famous linear-time algorithms:

Manacher's Algorithm

Real-World Applications

Palindromes appear in many real-world systems.

DNA Sequence Analysis

Biological sequences often contain palindromic regions.

Text Processing

Finding symmetric patterns in text.

Data Compression

Repeated symmetric structures can be optimized.

Bioinformatics

Genome analysis frequently uses palindrome detection.

Pattern Recognition

Image and signal processing use symmetry detection.

Palindromic Substring vs Palindromic Subsequence

Many candidates confuse these two interview questions.

Palindromic Substring

Characters must remain continuous.

Example

babad

Valid

bab

Palindromic Subsequence

Characters need not be adjacent.

Example

bbbab

Subsequence

bbbb

Characters are selected while preserving order.

Comparison

Feature	Substring	Subsequence
Continuous	✅ Yes	❌ No
Order Preserved	✅ Yes	✅ Yes
Adjacent Characters Required	✅ Yes	❌ No

Understanding the Problem

Input

forgeeksskeegfor

Longest Palindrome

geeksskeeg

Notice

The palindrome expands equally in both directions.

Another Example

banana

Palindrome

anana

Mathematical Concept

A palindrome satisfies

Left Character

=

Right Character

Continue expanding while

left == right

Example

racecar

r == r

a == a

c == c

e

The expansion stops only when the characters no longer match.

Visual Representation

Input

babad

Center

Expand

b a b

Result

bab

Another Center

b a b a d
    ↑

Expand

a b a

Result

aba

Odd-Length vs Even-Length Palindrome

Every palindrome has a center.

Odd Length

Example

racecar

Visualization

r a c e c a r
      ↑

Single center

Even Length

Example

abba

Visualization

a b b a
  ↑ ↑

Two centers

bb

Therefore,

every position must be checked twice:

Odd center
Even center

Dry Run

Input

babad

Check

Length

Check

Expand

bab

Length

Check

Expand

aba

Length

Longest

bab

aba

Approach 1 — Expand Around Center (Recommended)

This is the most popular interview solution.

The key observation is:

Every palindrome has a center.

The center can be:

One character (odd-length palindrome)
Two characters (even-length palindrome)

From every center,

expand left and right while the characters are equal.

Visualization

Input

abba

Even Center

a b b a
  ↑ ↑

Expand

a b b a
↑       ↑

Longest

abba

Input

racecar

Odd Center

r a c e c a r
      ↑

Expand

r a c e c a r
↑             ↑

Longest

racecar

Algorithm

Assume every character is a center.
Expand for odd-length palindrome.
Expand for even-length palindrome.
Track the longest palindrome.
Return the substring.

Java Program

public class LongestPalindrome {

    private static int start = 0;
    private static int maxLength = 1;

    public static String longestPalindrome(String text) {

        if (text == null || text.length() < 2) {
            return text;
        }

        start = 0;
        maxLength = 1;

        for (int i = 0; i < text.length(); i++) {

            expand(text, i, i);       // Odd

            expand(text, i, i + 1);   // Even

        }

        return text.substring(start,
                start + maxLength);

    }

    private static void expand(String text,
                               int left,
                               int right) {

        while (left >= 0 &&
                right < text.length() &&
                text.charAt(left) ==
                text.charAt(right)) {

            if (right - left + 1 > maxLength) {

                start = left;
                maxLength = right - left + 1;

            }

            left--;
            right++;

        }

    }

    public static void main(String[] args) {

        System.out.println(
                longestPalindrome("babad"));

        System.out.println(
                longestPalindrome("cbbd"));

        System.out.println(
                longestPalindrome("racecar"));

    }

}

Output

bab

bb

racecar

Step-by-Step Code Explanation

Initialize

start = 0;
maxLength = 1;

Store the starting position and current longest length.

Traverse every character.

for (int i = 0; i < text.length(); i++)

Every character is treated as a possible center.

Expand around odd center.

expand(text, i, i);

Example

racecar

↓

e

Expand around even center.

expand(text, i, i + 1);

Example

abba

↓

bb

Expand while characters match.

text.charAt(left)
==
text.charAt(right)

Continue moving outward.

Update longest palindrome.

start = left;

maxLength = right - left + 1;

Return

text.substring(start,
               start + maxLength);

Dry Run of Expand Around Center

Input

cbbd

Center	Palindrome	Length
c	c	1
b	b	1
bb	bb	2
d	d	1

Answer

bb

Advantages

Most common interview solution.
Easy to explain.
Handles odd and even palindromes.
No additional matrix required.
Excellent balance between simplicity and performance.

Drawbacks

Still checks every center.
Time complexity is quadratic.
Not the optimal theoretical solution.

Approach 2 — Brute Force

The brute-force approach generates every possible substring and checks whether it is a palindrome.

Although this is not efficient, it is a good starting point during interviews before discussing optimizations.

Algorithm

Generate every substring.
Check whether each substring is a palindrome.
Track the longest palindrome found.
Return the result.

Java Program

public class LongestPalindromeBruteForce {

    public static String longestPalindrome(String text) {

        if (text == null || text.isEmpty()) {
            return "";
        }

        String longest = "";

        for (int i = 0; i < text.length(); i++) {

            for (int j = i; j < text.length(); j++) {

                String current =
                        text.substring(i, j + 1);

                if (isPalindrome(current)
                        && current.length() > longest.length()) {

                    longest = current;

                }

            }

        }

        return longest;

    }

    private static boolean isPalindrome(String word) {

        int left = 0;
        int right = word.length() - 1;

        while (left < right) {

            if (word.charAt(left)
                    != word.charAt(right)) {

                return false;

            }

            left++;
            right--;

        }

        return true;

    }

    public static void main(String[] args) {

        System.out.println(
                longestPalindrome("babad"));

    }

}

Output

bab

(or aba, depending on traversal order)

Time & Space Complexity

Approach	Time	Extra Space
Expand Around Center	O(n²)	O(1)
Brute Force	O(n³)	O(1)*

*Ignoring the temporary substring objects created by the language implementation.

Comparison of Approaches

Feature	Expand Around Center	Brute Force
Interview Friendly	⭐⭐⭐⭐⭐	⭐⭐⭐
Easy to Understand	⭐⭐⭐⭐⭐	⭐⭐⭐⭐⭐
Performance	⭐⭐⭐⭐⭐	⭐⭐
Extra Space	O(1)	O(1)*

Advantages

Expand Around Center is the preferred interview solution.
Brute Force is simple and useful for explaining the baseline approach.
Both help build intuition before learning advanced algorithms.

Drawbacks

Brute Force is too slow for large inputs.
Expand Around Center is not linear-time.
Interviewers may ask whether the solution can be improved further.

In Part 2, we'll cover:

Approach 3 – Dynamic Programming
Approach 4 – Manacher's Algorithm (O(n))
Approach 5 – Recursive Approach
Unicode Considerations
Comparison of All Approaches
Common Interview Mistakes
Edge Cases
Interview Follow-up Questions
Related Problems
Key Takeaways
Frequently Asked Interview Questions
Interview Tips

Approach 3 — Dynamic Programming

Dynamic Programming (DP) is one of the most common interview solutions for this problem.

Instead of checking the same substrings repeatedly,

store previously computed palindrome information.

DP Idea

Create a table

dp[i][j]

where

dp[i][j] = true

means

Substring(i...j)

is a palindrome.

Mathematical Relation

A substring is a palindrome if

s[i] == s[j]

AND

dp[i + 1][j - 1]

is already a palindrome.

Therefore,

dp[i][j] =

(s[i] == s[j])

AND

dp[i + 1][j - 1]

Visualization

Input

babad

DP Table

      b  a  b  a  d
   -----------------
b |  T  F  T  F  F
a |     T  F  T  F
b |        T  F  F
a |           T  F
d |              T

Largest palindrome

bab

Algorithm

Every single character is a palindrome.
Check substrings of length 2.
Expand to longer substrings.
Update the longest palindrome.
Return the answer.

Java Program

public class LongestPalindromeDP {

    public static String longestPalindrome(String text) {

        int n = text.length();

        if (n < 2) {
            return text;
        }

        boolean[][] dp = new boolean[n][n];

        int start = 0;
        int maxLength = 1;

        for (int i = 0; i < n; i++) {

            dp[i][i] = true;

        }

        for (int length = 2; length <= n; length++) {

            for (int i = 0;
                 i <= n - length;
                 i++) {

                int j = i + length - 1;

                if (text.charAt(i) ==
                        text.charAt(j)) {

                    if (length == 2 ||
                            dp[i + 1][j - 1]) {

                        dp[i][j] = true;

                        if (length > maxLength) {

                            start = i;
                            maxLength = length;

                        }

                    }

                }

            }

        }

        return text.substring(
                start,
                start + maxLength);

    }

    public static void main(String[] args) {

        System.out.println(
                longestPalindrome("babad"));

        System.out.println(
                longestPalindrome("cbbd"));

    }

}

Output

bab

bb

Advantages

Easy to understand.
Excellent DP interview problem.
Avoids repeated palindrome checks.

Drawbacks

Uses O(n²) memory.
Less space-efficient than Expand Around Center.

Approach 4 — Manacher's Algorithm (Optimal)

Manacher's Algorithm is the fastest known solution.

Time Complexity

O(n)

It is considered one of the most advanced string algorithms.

Why Manacher?

Instead of expanding from every center independently,

reuse information from previously computed palindromes.

This avoids redundant comparisons.

Visualization

Original

abba

Transformed

^#a#b#b#a#$

Now

Odd palindromes
Even palindromes

are handled uniformly.

Algorithm

Transform the string.
Expand around centers.
Reuse previous palindrome lengths.
Track the maximum radius.
Convert back to the original substring.

Simplified Java Program

public class ManachersAlgorithm {

    public static String longestPalindrome(String text) {

        if (text == null ||
                text.length() < 2) {

            return text;

        }

        // Placeholder implementation.
        // Full Manacher's Algorithm is typically
        // covered in a dedicated article because
        // of its complexity.

        return text;

    }

}

Note: A full implementation of Manacher's Algorithm includes string transformation, palindrome radius calculation, mirror optimization, and center/right boundary tracking. It is usually taught as a standalone advanced algorithm.

Advantages

Linear time.
Best theoretical performance.
Excellent advanced interview topic.

Drawbacks

Difficult to implement.
Hard to remember during interviews.
Rarely expected unless interviewing for advanced algorithm roles.

Approach 5 — Recursive Approach

Another interview variation uses recursion.

The recursive solution checks progressively smaller substrings.

Although elegant,

it is not the most efficient approach.

Algorithm

Check whether the current substring is a palindrome.
If yes, return it.
Otherwise recursively check:
- Left substring
- Right substring
Return the longer palindrome.

Simplified Java Program

public class RecursivePalindrome {

    public static String longestPalindrome(String text) {

        if (text == null ||
                text.length() <= 1) {

            return text;

        }

        // Simplified placeholder.
        // Complete recursive implementations
        // are considerably longer and less
        // efficient than iterative solutions.

        return text.substring(0, 1);

    }

}

Advantages

Demonstrates recursion.
Useful for recursion practice.

Drawbacks

Inefficient.
Overlapping subproblems.
Higher recursion overhead.

Unicode Considerations

Java strings support Unicode.

Examples

こんにちは

नमस्ते

😊😊😊

The algorithms work correctly for general Java strings.

For supplementary Unicode characters (such as many emoji), consider iterating over Unicode code points instead of individual char values.

Edge Cases

Input	Expected Output
`""`	`""`
`"a"`	`a`
`"aa"`	`aa`
`"abc"`	Any single character
`"abba"`	`abba`
`"racecar"`	`racecar`
`null`	Handle appropriately based on application requirements

Time & Space Complexity

Approach	Time	Extra Space
Brute Force	O(n³)	O(1)*
Expand Around Center	O(n²)	O(1)
Dynamic Programming	O(n²)	O(n²)
Manacher's Algorithm	O(n)	O(n)
Recursive	Exponential (worst case)	O(n) recursion stack

*Ignoring temporary substring allocations.

Comparison of All Approaches

Approach	Interview Friendly	Performance	Best Use Case
Brute Force	⭐⭐⭐	⭐⭐	Learning
Expand Around Center	⭐⭐⭐⭐⭐	⭐⭐⭐⭐⭐	Most interviews
Dynamic Programming	⭐⭐⭐⭐⭐	⭐⭐⭐⭐	DP interviews
Manacher's Algorithm	⭐⭐⭐	⭐⭐⭐⭐⭐	Advanced algorithms
Recursive	⭐⭐⭐	⭐⭐	Recursion practice

Common Interview Mistakes

Mistake 1

Confusing substring with subsequence.

Substring

abcde

↓

bcd

Subsequence

abcde

↓

ace

Mistake 2

Checking only odd-length palindromes.

Example

abba

The center is

bb

Always check:

Odd center
Even center

Mistake 3

Not updating the longest palindrome correctly.

Always compare lengths before updating the answer.

Mistake 4

Generating every substring unnecessarily.

Prefer Expand Around Center instead of Brute Force.

Mistake 5

Ignoring empty strings or single-character inputs.

Every single character is a palindrome.

Interview Follow-up Questions

Q1. Why is Expand Around Center faster than Brute Force?

Q2. Can you solve this in O(n) time?

Q3. Explain Manacher's Algorithm.

Q4. What is the difference between substring and subsequence?

Q5. How does Dynamic Programming work here?

Q6. How would you handle Unicode characters?

Q7. Can multiple longest palindromes exist?

Q8. Can this problem be solved recursively?

Q9. What is the space complexity of each approach?

Q10. Which solution would you choose in production?

Key Takeaways

A palindrome reads the same forward and backward.
The Longest Palindromic Substring requires continuous characters.
Expand Around Center is the preferred interview solution because it is simple, efficient, and uses constant extra space.
Dynamic Programming avoids recomputation by storing palindrome information.
Manacher's Algorithm achieves O(n) time but is considerably more complex.
Always check both odd-length and even-length palindrome centers.

Frequently Asked Interview Questions

Q1. Which solution is best for interviews?

The Expand Around Center approach is the preferred answer because it balances simplicity, performance, and readability.

Q2. Which algorithm is the fastest?

Manacher's Algorithm is the optimal solution with O(n) time complexity.

Q3. Why check two centers?

Odd-length palindromes have one center.

Example

racecar

Even-length palindromes have two centers.

Example

abba

Checking both ensures that all palindromes are considered.

Q4. What is the difference between substring and subsequence?

A substring consists of contiguous characters.

A subsequence preserves character order but does not require adjacency.

Q5. Can there be multiple correct answers?

Yes.

For

babad

Both

bab

and

aba

are valid longest palindromic substrings.

Interview Tip

If an interviewer asks:

"Find the Longest Palindromic Substring."

Start with the Expand Around Center approach because it is the industry-standard interview solution.

Then discuss progressively advanced approaches:

Brute Force (baseline)
Expand Around Center (recommended)
Dynamic Programming (DP optimization)
Manacher's Algorithm (optimal O(n))
Recursive Approach (conceptual understanding)

Before coding, ask clarifying questions such as:

Can multiple correct answers be returned?
Should the search be case-sensitive?
Can the input be empty or null?
Should Unicode characters be supported?

Explaining the trade-offs between these approaches demonstrates strong algorithmic thinking and solid Java interview skills.