Longest Palindromic Substring in DSA Java - Execution Trace

Concept Flow - Longest Palindromic Substring

Start at each index i in string

↓

Expand around center i (odd length)

↓

Expand around center i and i+1 (even length)

↓

Check palindrome length

↓

Update longest palindrome if longer

↓

Move to next index i+1

↓

Repeat until end of string

↓

Return longest palindrome substring

Check each position as center, expand outwards to find palindromes, track longest found.

Execution Sample

DSA Java

public String longestPalindrome(String s) {
  int start = 0, end = 0;
  for (int i = 0; i < s.length(); i++) {
    int len1 = expandAroundCenter(s, i, i);
    int len2 = expandAroundCenter(s, i, i + 1);
    int len = Math.max(len1, len2);
    if (len > end - start + 1) {
      start = i - (len - 1) / 2;
      end = i + len / 2;
    }
  }
  return s.substring(start, end + 1);
}

private int expandAroundCenter(String s, int left, int right) {
  while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
    left--;
    right++;
  }
  return right - left - 1;
}

Find longest palindrome by expanding around each center in the string.

Execution Table

Step	Operation	Center Indices	Palindrome Length Found	Longest Palindrome Indices	Longest Palindrome Substring
1	Expand around center (0,0)	(0,0)	1	[0,0]	"a"
2	Expand around center (0,1)	(0,1)	0	[0,0]	"a"
3	Expand around center (1,1)	(1,1)	1	[0,0]	"a"
4	Expand around center (1,2)	(1,2)	0	[0,0]	"a"
5	Expand around center (2,2)	(2,2)	3	[1,3]	"bab"
6	Expand around center (2,3)	(2,3)	0	[1,3]	"bab"
7	Expand around center (3,3)	(3,3)	1	[1,3]	"bab"
8	Expand around center (3,4)	(3,4)	0	[1,3]	"bab"
9	Expand around center (4,4)	(4,4)	1	[1,3]	"bab"
10	Expand around center (4,5)	(4,5)	0	[1,3]	"bab"
11	Expand around center (5,5)	(5,5)	1	[1,3]	"bab"
12	Expand around center (5,6)	(5,6)	0	[1,3]	"bab"
13	Expand around center (6,6)	(6,6)	1	[1,3]	"bab"
14	Expand around center (6,7)	(6,7)	0	[1,3]	"bab"
15	Expand around center (7,7)	(7,7)	1	[1,3]	"bab"
16	End of string reached	-	-	[1,3]	"bab"

💡 All centers expanded, longest palindrome found at indices [1,3]

Variable Tracker

Variable	Start	After Step 1	After Step 5	After Step 16	Final
start	0	0	1	1	1
end	0	0	3	3	3
i (center index)	0	0	2	7	7
len (palindrome length)	0	1	3	1	1

Key Moments - 3 Insights

Why do we check two centers (i,i) and (i,i+1)?

Because palindromes can be odd length (center at one char) or even length (center between two chars). See execution_table rows 1 and 2 for example.

Why does the palindrome length calculation subtract 1 after expanding?

Because the while loop expands one step too far before stopping. The length is right - left - 1 to correct for that. See expandAroundCenter method in code.

How do we update start and end indices for the longest palindrome?

We calculate start as i - (len-1)/2 and end as i + len/2 to get correct substring boundaries. See execution_table row 5 where longest palindrome updates.

Visual Quiz - 3 Questions

Look at the execution_table at step 5, what is the longest palindrome substring found?

A "aba"

B "bab"

C "a"

D "b"

💡 Hint

Check the 'Longest Palindrome Substring' column at step 5 in execution_table.

At which step does the longest palindrome length first become greater than 1?

A Step 1

B Step 3

C Step 5

D Step 7

💡 Hint

Look at the 'Palindrome Length Found' column and when it first exceeds 1.

If the input string was "aaaa", how would the longest palindrome length at center (1,2) change?

A It would be 4

B It would be 3

C It would be 2

D It would be 1

💡 Hint

Consider expanding around centers for repeated characters, check expandAroundCenter logic.

Concept Snapshot

Longest Palindromic Substring:
- Check each index as center
- Expand around center for odd and even length palindromes
- Track longest palindrome start and end indices
- Return substring from start to end
- Time complexity O(n^2), space O(1)

Full Transcript

The Longest Palindromic Substring algorithm checks each character index as a center and expands outwards to find palindromes. It considers both odd length palindromes (center at one character) and even length palindromes (center between two characters). For each center, it expands while characters on both sides match. It tracks the longest palindrome found by updating start and end indices. Finally, it returns the substring between these indices. The execution table shows step-by-step expansions and updates. Key moments clarify why two centers are checked, how length is calculated, and how indices are updated. The visual quiz tests understanding of palindrome lengths and updates during execution.

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