Longest Palindromic Substring in DSA Java

Mental Model

Find the longest part of a string that reads the same forwards and backwards by expanding around each center.

Analogy: Imagine looking for the biggest mirror reflection in a row of letters by checking from the middle outwards on both sides.

s = "b a b a d"
indexes: 0 1 2 3 4
Check centers at each index and between indexes:

b a b a d
↑
center at index 0

b a b a d
  ↑
center between index 0 and 1

b a b a d
    ↑
center at index 2

Each center tries to expand left and right to find palindrome.

Dry Run Walkthrough

Input: string: "babad"

Goal: Find the longest substring that reads the same forwards and backwards

Step 1: Check center at index 0 ('b'), expand left and right

"b" is palindrome, expand fails beyond boundaries

Why: Single letter is always palindrome, start from here

Step 2: Check center between index 0 and 1 ('b' and 'a'), no palindrome longer than 1

"b" and "a" differ, no expansion

Why: Even length palindrome check

Step 3: Check center at index 1 ('a'), expand left and right to include 'b' at index 0 and 'b' at index 2

"bab" is palindrome after expansion

Why: Found palindrome longer than previous

Step 4: Check center between index 1 and 2 ('a' and 'b'), no palindrome longer than 1

"a" and "b" differ, no expansion

Why: Even length palindrome check

Step 5: Check center at index 2 ('b'), expand left and right to include 'a' at index 1 and 'a' at index 3

"aba" is palindrome after expansion

Why: Another palindrome of length 3 found

Step 6: Check center between index 2 and 3 ('b' and 'a'), no palindrome longer than 1

"b" and "a" differ, no expansion

Why: Even length palindrome check

Step 7: Check center at index 3 ('a'), expand left and right but no longer palindrome than 1

"a" palindrome only

Why: Single letter palindrome

Step 8: Check center between index 3 and 4 ('a' and 'd'), no palindrome longer than 1

"a" and "d" differ, no expansion

Why: Even length palindrome check

Step 9: Check center at index 4 ('d'), single letter palindrome

"d" palindrome only

Why: Single letter palindrome

Result:

Longest palindrome substring is "bab" or "aba"

Annotated Code

DSA Java

public class LongestPalindromicSubstring {

    public static String longestPalindrome(String s) {
        if (s == null || s.length() < 1) return "";
        int start = 0, end = 0;
        for (int i = 0; i < s.length(); i++) {
            int len1 = expandAroundCenter(s, i, i);       // odd length palindrome
            int len2 = expandAroundCenter(s, i, i + 1);   // even length palindrome
            int len = Math.max(len1, len2);
            if (len > end - start) {
                start = i - (len - 1) / 2;               // update start index
                end = i + len / 2;                         // update end index
            }
        }
        return s.substring(start, end + 1);
    }

    private static int expandAroundCenter(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;                                    // expand left pointer outward
            right++;                                   // expand right pointer outward
        }
        return right - left - 1;                        // length of palindrome
    }

    public static void main(String[] args) {
        String input = "babad";
        System.out.println(longestPalindrome(input));
    }
}

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

iterate over each character as potential palindrome center

int len1 = expandAroundCenter(s, i, i);

check odd length palindrome centered at i

int len2 = expandAroundCenter(s, i, i + 1);

check even length palindrome centered between i and i+1

int len = Math.max(len1, len2);

choose longer palindrome length from odd or even center

if (len > end - start) {

update longest palindrome boundaries if longer found

start = i - (len - 1) / 2;

calculate new start index of palindrome

end = i + len / 2;

calculate new end index of palindrome

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

expand pointers outward while characters match

return right - left - 1;

return length of palindrome found

Output

aba

Complexity Analysis

Time: O(n^2) because for each character we expand outwards which can take up to n steps

Space: O(1) because we only use a few variables to track indices and lengths

vs Alternative: Compared to checking all substrings (O(n^3)), this approach is faster by expanding around centers

Edge Cases

empty string

returns empty string immediately

DSA Java

if (s == null || s.length() < 1) return "";

string with all identical characters

returns the entire string as palindrome

DSA Java

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

string with no palindrome longer than 1

returns any single character substring

DSA Java

int len1 = expandAroundCenter(s, i, i);

When to Use This Pattern

When asked to find the longest substring that reads the same forwards and backwards, use the expand around center pattern because it efficiently checks palindromes from the middle outwards.

Common Mistakes

Mistake: Only checking odd length palindromes and missing even length ones
Fix: Check both odd (i, i) and even (i, i+1) centers for palindromes

Mistake: Incorrectly calculating start and end indices after expansion
Fix: Use formulas start = i - (len - 1) / 2 and end = i + len / 2 to get correct boundaries

Summary

Finds the longest substring that reads the same forwards and backwards by expanding around centers.

Use when you need to find the longest palindromic substring efficiently without checking all substrings.

The key insight is to treat each character and gap between characters as a center and expand outwards to find palindromes.

Practice

1. What is the main goal of the Longest Palindromic Substring problem?

easy

A. Find the longest substring with all unique characters

B. Find the longest substring with increasing characters

C. Find the longest substring that reads the same forwards and backwards

D. Find the longest substring that contains only vowels

Solution

1. Step 1: Understand the problem definition

   The problem asks to find a substring that is a palindrome, meaning it reads the same forwards and backwards.

2. Step 2: Identify the goal

   Among all palindromic substrings, we want the one with the maximum length.

3. Final Answer:

   Find the longest substring that reads the same forwards and backwards -> Option C

4. Quick Check:

   Longest Palindromic Substring = Find palindrome substring [OK]

Hint: Look for substring that mirrors itself [OK]

Common Mistakes:

• Confusing palindrome with unique characters
• Looking for longest substring without repeats
• Thinking about character order increasing

2. Which of the following Java method signatures is correct for a function that returns the longest palindromic substring from a given string s?

easy

A. public String longestPalindrome(String s)

B. public void longestPalindrome(String s)

C. public int longestPalindrome(String s)

D. public String longestPalindrome(int s)

Solution

1. Step 1: Analyze the return type

   The function should return the longest palindromic substring, which is a String.

2. Step 2: Check parameter type

   The input is a string, so the parameter should be of type String.

3. Final Answer:

   public String longestPalindrome(String s) -> Option A

4. Quick Check:

   Return type String and parameter String = public String longestPalindrome(String s) [OK]

Hint: Return type matches output, parameter matches input [OK]

Common Mistakes:

• Using void return type when output is needed
• Using int parameter instead of String
• Returning int instead of String

3. What will be the output of the following Java code snippet?

public class Test {
  public static String longestPalindrome(String s) {
    int start = 0, maxLen = 1;
    for (int i = 0; i < s.length(); i++) {
      for (int j = i; j < s.length(); j++) {
        String sub = s.substring(i, j + 1);
        if (isPalindrome(sub) && sub.length() > maxLen) {
          start = i;
          maxLen = sub.length();
        }
      }
    }
    return s.substring(start, start + maxLen);
  }

  private static boolean isPalindrome(String str) {
    int left = 0, right = str.length() - 1;
    while (left < right) {
      if (str.charAt(left++) != str.charAt(right--)) return false;
    }
    return true;
  }

  public static void main(String[] args) {
    System.out.println(longestPalindrome("babad"));
  }
}

medium

A. "babad"

B. "aba"

C. "bad"

D. "bab"

Solution

1. Step 1: Understand the code logic

   The code checks all substrings and updates the longest palindrome found.

2. Step 2: Trace the input "babad"

   Palindromic substrings include "bab" and "aba" both length 3. The code picks the first found longest palindrome, which is "bab".

3. Final Answer:

   "bab" -> Option D

4. Quick Check:

   First longest palindrome found = "bab" [OK]

Hint: Check first longest palindrome substring found [OK]

Common Mistakes:

• Assuming "aba" is returned instead of "bab"
• Thinking entire string is palindrome
• Ignoring substring length comparison

4. Identify the bug in the following code snippet for finding the longest palindromic substring:

public String longestPalindrome(String s) {
  int maxLen = 0, start = 0;
  for (int i = 0; i < s.length(); i++) {
    for (int j = i; j < s.length(); j++) {
      String sub = s.substring(i, j);
      if (isPalindrome(sub) && sub.length() > maxLen) {
        maxLen = sub.length();
        start = i;
      }
    }
  }
  return s.substring(start, start + maxLen);
}

medium

A. The loop should start from j = i + 1

B. The substring end index should be j + 1, not j

C. maxLen should be initialized to 1, not 0

D. The isPalindrome method is missing

Solution

1. Step 1: Check substring usage

   Java substring method excludes the end index, so substring(i, j) misses character at j.

2. Step 2: Correct substring end index

   It should be substring(i, j + 1) to include character at position j.

3. Final Answer:

   The substring end index should be j + 1, not j -> Option B

4. Quick Check:

   substring(i, j + 1) includes full substring [OK]

Hint: Remember substring excludes end index [OK]

Common Mistakes:

• Using substring(i, j) which excludes last char
• Not updating maxLen correctly
• Ignoring substring indexing rules

5. Given the string "forgeeksskeegfor", which approach will efficiently find the longest palindromic substring and what is the substring?

hard

A. Dynamic programming with memoization; longest palindrome is "geeksskeeg"

B. Brute force checking all substrings; longest palindrome is "forgeeksskeegfor"

C. Expand around center approach; longest palindrome is "sskeeg"

D. Sorting characters and checking; longest palindrome is "sskeeg"

Solution

1. Step 1: Identify efficient methods

   Dynamic programming and expand around center are efficient for this problem; brute force is slow.

2. Step 2: Check longest palindrome in given string

   "geeksskeeg" is the longest palindromic substring inside "forgeeksskeegfor".

3. Step 3: Match approach and answer

   Dynamic programming with memoization is a common efficient approach returning "geeksskeeg".

4. Final Answer:

   Dynamic programming with memoization; longest palindrome is "geeksskeeg" -> Option A

5. Quick Check:

   DP approach finds "geeksskeeg" efficiently [OK]

Hint: Use DP or center expansion for efficiency [OK]

Common Mistakes:

• Assuming entire string is palindrome
• Using brute force for large strings
• Sorting characters loses substring order