Longest Palindromic Substring in DSA Go - Execution Trace

Concept Flow - Longest Palindromic Substring

Start with each character as center

↓

Expand around center

↓

Check left==right?

↓

Expand pointers left--, right++

↓

Update longest if found

↓

Move to next center

↓

Done

We check each character (and gap between characters) as a center and expand outwards to find palindromes, updating the longest found.

Execution Sample

DSA Go

func longestPalindrome(s string) string {
  start, end := 0, 0
  for i := 0; i < len(s); i++ {
    len1 := expandAroundCenter(s, i, i)
    len2 := expandAroundCenter(s, i, i+1)
    length := max(len1, len2)
    if length > end-start {
      start = i - (length-1)/2
      end = i + length/2
    }
  }
  return s[start : end+1]
}

func expandAroundCenter(s string, left int, right int) int {
  for left >= 0 && right < len(s) && s[left] == s[right] {
    left--
    right++
  }
  return right - left - 1
}

func max(a, b int) int {
  if a > b {
    return a
  }
  return b
}

This code finds the longest palindromic substring by expanding around each center.

Execution Table

Step	Operation	Center Indices	Palindrome Length Found	Longest Start-End	Current Longest Substring
1	Expand around center (i=0, single center)	left=0, right=0	1	start=0, end=0	"a"
2	Expand around center (i=0, double center)	left=0, right=1	0	start=0, end=0	"a"
3	Expand around center (i=1, single center)	left=1, right=1	1	start=0, end=0	"a"
4	Expand around center (i=1, double center)	left=1, right=2	0	start=0, end=0	"a"
5	Expand around center (i=2, single center)	left=2, right=2	3	start=1, end=3	"bab"
6	Expand around center (i=2, double center)	left=2, right=3	0	start=1, end=3	"bab"
7	Expand around center (i=3, single center)	left=3, right=3	1	start=1, end=3	"bab"
8	Expand around center (i=3, double center)	left=3, right=4	0	start=1, end=3	"bab"
9	Expand around center (i=4, single center)	left=4, right=4	1	start=1, end=3	"bab"
10	Expand around center (i=4, double center)	left=4, right=5	0	start=1, end=3	"bab"
11	Expand around center (i=5, single center)	left=5, right=5	1	start=1, end=3	"bab"
12	Expand around center (i=5, double center)	left=5, right=6	0	start=1, end=3	"bab"
13	Expand around center (i=6, single center)	left=6, right=6	1	start=1, end=3	"bab"
14	Expand around center (i=6, double center)	left=6, right=7	0	start=1, end=3	"bab"
15	End of string reached	-	-	start=1, end=3	"bab"

💡 All centers checked, longest palindrome found is "bab" from index 1 to 3.

Variable Tracker

Variable	Start	After Step 5	After Step 15
start	0	1	1
end	0	3	3
i	0	2	6
length	varies	3	1

Key Moments - 3 Insights

Why do we check two centers (single and double) for each index?

Because palindromes can be odd length (single center) or even length (double center). See execution_table steps 1 and 2 for i=0.

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

We calculate start as i - (length-1)/2 and end as i + length/2 when a longer palindrome is found (see step 5). This centers the palindrome correctly.

Why does the palindrome length sometimes become 0?

When the characters at left and right pointers don't match, expansion stops immediately, resulting in length 0 (see steps 2,4).

Visual Quiz - 3 Questions

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

A 3

B 1

C 0

D 2

💡 Hint

Check the 'Palindrome Length Found' column at step 5 in execution_table.

At which step does the longest palindrome substring update from "a" to "bab"?

A Step 3

B Step 5

C Step 7

D Step 1

💡 Hint

Look at the 'Current Longest Substring' column and see when it changes to "bab".

If the input string was "abba", which center expansion would find the longest palindrome?

A Single center at i=1

B Double center at i=1

C Single center at i=2

D Double center at i=2

💡 Hint

Even length palindrome "abba" is found by expanding around double center between indices 1 and 2.

Concept Snapshot

Longest Palindromic Substring:
- Check each index as center (single and double)
- Expand pointers left and right while chars match
- Update longest substring start and end indices
- Return substring from start to end
- Handles odd and even length palindromes

Full Transcript

The longest palindromic substring problem finds the biggest substring that reads the same forwards and backwards. We do this by checking each character and the gap between characters as centers. For each center, we expand outwards while the characters on both sides match. We keep track of the longest palindrome found by updating start and end indices. This method works for both odd and even length palindromes. The execution table shows each expansion step, the palindrome length found, and updates to the longest substring. Key moments include why we check two centers per index and how we calculate the substring indices. The final longest palindrome is returned after checking all centers.

Practice

1. What is the main goal when finding the Longest Palindromic Substring in a given string?

easy

A. To find the longest continuous sequence of characters that reads the same backward and forward

B. To find the longest substring with all unique characters

C. To find the longest substring that contains only vowels

D. To find the longest substring that starts and ends with the same character

Solution

1. Step 1: Understand palindrome definition

   A palindrome reads the same backward and forward, like 'madam' or 'racecar'.

2. Step 2: Identify longest continuous palindrome

   The problem asks for the longest continuous substring that is a palindrome, not just any substring or character pattern.

3. Final Answer:

   To find the longest continuous sequence of characters that reads the same backward and forward -> Option A

4. Quick Check:

   Longest palindromic substring = continuous palindrome [OK]

Hint: Look for continuous sequences that mirror around center [OK]

Common Mistakes:

• Confusing substring with subsequence
• Looking for unique characters instead of palindrome
• Ignoring continuity of substring

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

easy

A. func longestPalindrome(s int) string

B. func longestPalindrome(s string) string

C. func longestPalindrome(s string) int

D. func longestPalindrome() string

Solution

1. Step 1: Check input parameter type

   The input should be a string to find its palindromic substring, so parameter type must be string.

2. Step 2: Check return type

   The function returns the longest palindromic substring, which is a string, so return type must be string.

3. Final Answer:

   func longestPalindrome(s string) string -> Option B

4. Quick Check:

   Input string, output string [OK]

Hint: Input and output both are strings for palindrome substring [OK]

Common Mistakes:

• Using wrong input type like int
• Returning int instead of string
• Missing input parameter

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

package main
import "fmt"

func longestPalindrome(s string) string {
    start, maxLen := 0, 1
    for i := 0; i < len(s); i++ {
        for j := i; j < len(s); j++ {
            sub := s[i : j+1]
            if isPalindrome(sub) && len(sub) > maxLen {
                start = i
                maxLen = len(sub)
            }
        }
    }
    return s[start : start+maxLen]
}

func isPalindrome(str string) bool {
    for i := 0; i < len(str)/2; i++ {
        if str[i] != str[len(str)-1-i] {
            return false
        }
    }
    return true
}

func main() {
    fmt.Println(longestPalindrome("babad"))
}

medium

A. "bab"

B. "aba"

C. "bad"

D. "babad"

Solution

1. Step 1: Understand the code logic

   The code checks all substrings and updates the longest palindrome found. For "babad", "bab" and "aba" are both palindromes of length 3.

2. Step 2: Check which palindrome is returned

   The code updates start and maxLen when a longer palindrome is found. It finds "bab" first and keeps it because "aba" comes later but has the same length, so "bab" remains.

3. Final Answer:

   "bab" -> Option A

4. Quick Check:

   First longest palindrome found = "bab" [OK]

Hint: Check first longest palindrome found in order [OK]

Common Mistakes:

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

4. The following Go code attempts to find the longest palindromic substring but has a bug. What is the bug?

func longestPalindrome(s string) string {
    start, maxLen := 0, 1
    for i := 0; i < len(s); i++ {
        for j := i; j < len(s); j++ {
            sub := s[i:j]
            if isPalindrome(sub) && len(sub) > maxLen {
                start = i
                maxLen = len(sub)
            }
        }
    }
    return s[start : start+maxLen]
}

medium

A. The function isPalindrome is missing

B. The loop should start from j = i+1 instead of j = i

C. maxLen should be initialized to 0 instead of 1

D. The substring slice should be s[i:j+1] to include character at index j

Solution

1. Step 1: Check substring slicing

   In Go, s[i:j] excludes character at index j, so substring misses last character.

2. Step 2: Correct slicing to include last character

   Changing to s[i:j+1] includes character at j, ensuring full substring is checked.

3. Final Answer:

   The substring slice should be s[i:j+1] to include character at index j -> Option D

4. Quick Check:

   Substring slicing excludes last char if j not incremented [OK]

Hint: Remember Go slices exclude end index, use j+1 [OK]

Common Mistakes:

• Using s[i:j] misses last character
• Not adjusting loop indices accordingly
• Assuming isPalindrome is missing

5. Given the string s = "forgeeksskeegfor", which approach below efficiently finds the longest palindromic substring and what is that substring?

hard

A. Expand around center approach; longest palindrome is "forgeeksskeegfor"

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

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

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

Solution

1. Step 1: Identify efficient methods

   Dynamic programming stores palindrome info to avoid repeated checks, efficient for this problem.

2. Step 2: Find longest palindrome in given string

   "geeksskeeg" is the longest palindromic substring inside "forgeeksskeegfor"; entire string is not palindrome.

3. Final Answer:

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

4. Quick Check:

   DP finds "geeksskeeg" efficiently [OK]

Hint: Use DP or expand center for efficient palindrome search [OK]

Common Mistakes:

• Assuming entire string is palindrome
• Using brute force which is slow
• Sorting characters breaks substring continuity