Longest Palindromic Substring in DSA Go

Mental Model

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

Analogy: Imagine looking for the biggest mirror in a hallway where the reflection looks exactly the same from both sides.

s = "b a b a d"
indexes: 0 1 2 3 4
Check centers:
  ↑
  b
  a
  b
  a
  d

Dry Run Walkthrough

Input: string: "babad"

Goal: Find the longest substring that is a palindrome

Step 1: Check palindrome centered at index 0 (odd length)

"b" -> palindrome length 1

Why: Every single character is a palindrome of length 1

Step 2: Check palindrome centered between index 0 and 1 (even length)

"b a" -> no palindrome longer than 1

Why: Check even length palindromes by expanding around two centers

Step 3: Check palindrome centered at index 1 (odd length)

"a b a" -> palindrome length 3

Why: Expand around center 1 to find palindrome 'aba'

Step 4: Check palindrome centered between index 1 and 2 (even length)

"a b" -> no palindrome longer than 1

Why: No even length palindrome here

Step 5: Check palindrome centered at index 2 (odd length)

"b a b" -> palindrome length 3 (same as before)

Why: Another palindrome 'bab' found

Step 6: Check palindrome centered between index 2 and 3 (even length)

"b a" -> no palindrome longer than 1

Why: No even length palindrome here

Step 7: Check palindrome centered at index 3 (odd length)

"a" -> palindrome length 1

Why: Single character palindrome

Step 8: Check palindrome centered between index 3 and 4 (even length)

"a d" -> no palindrome longer than 1

Why: No even length palindrome here

Step 9: Check palindrome centered at index 4 (odd length)

"d" -> palindrome length 1

Why: Single character palindrome

Result:

"bab" or "aba" is the longest palindromic substring

Annotated Code

DSA Go

package main

import (
	"fmt"
)

func longestPalindrome(s string) string {
	if len(s) == 0 {
		return ""
	}
	start, end := 0, 0

	// expandAroundCenter tries to expand palindrome around left and right indices
	expandAroundCenter := func(left, right int) int {
		for left >= 0 && right < len(s) && s[left] == s[right] {
			left--
			right++
		}
		return right - left - 1 // length of palindrome
	}

	for i := 0; i < len(s); i++ {
		len1 := expandAroundCenter(i, i)     // odd length palindrome
		len2 := expandAroundCenter(i, i+1)   // even length palindrome
		maxLen := len1
		if len2 > len1 {
			maxLen = len2
		}
		if maxLen > end-start {
			start = i - (maxLen-1)/2
			end = i + maxLen/2
		}
	}
	return s[start : end+1]
}

func main() {
	input := "babad"
	result := longestPalindrome(input)
	fmt.Println(result)
}

for left >= 0 && right < len(s) && s[left] == s[right] {

expand palindrome by moving left and right pointers outward while characters match

return right - left - 1

calculate length of palindrome found by expansion

len1 := expandAroundCenter(i, i)

check odd length palindrome centered at i

len2 := expandAroundCenter(i, i+1)

check even length palindrome centered between i and i+1

if maxLen > end-start {

update start and end indices if longer palindrome found

start = i - (maxLen-1)/2

calculate new start index of palindrome

end = i + maxLen/2

calculate new end index of palindrome

Output

bab

Complexity Analysis

Time: O(n^2) because for each character we expand around centers which can take up to O(n) time

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

vs Alternative: Compared to dynamic programming O(n^2) with O(n^2) space, this approach uses less memory and is simpler

Edge Cases

empty string

returns empty string immediately

DSA Go

if len(s) == 0 {
	return ""
}

string with all identical characters

returns the entire string as palindrome

DSA Go

for left >= 0 && right < len(s) && s[left] == s[right] {

string with no palindrome longer than 1

returns any single character substring

DSA Go

if maxLen > end-start {

When to Use This Pattern

When asked to find the longest substring with a symmetric property, try expanding around centers to find palindromes efficiently.

Common Mistakes

Mistake: Only checking odd length palindromes and missing even length ones
Fix: Check both odd and even length palindromes by expanding around one center and two centers

Mistake: Not updating start and end indices correctly leading to wrong substring
Fix: Calculate start and end using the formula with maxLen and current center index

Summary

Finds the longest substring that reads the same forwards and backwards.

Use when you need to find the biggest palindrome inside a string.

Check palindromes by expanding around each character and between characters.

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