Longest Palindromic Substring in DSA Go - Build from Scratch

Longest Palindromic Substring

📖 Scenario: You are working on a text analysis tool that finds the longest palindrome inside a given word or sentence. A palindrome is a sequence of characters that reads the same backward as forward, like "racecar" or "level".This tool helps users discover interesting patterns in their text inputs.

🎯 Goal: Build a Go program that finds the longest palindromic substring inside a given string.You will create the input string, set up helper variables, write the core logic to find the longest palindrome, and finally print the result.

📋 What You'll Learn

Create a string variable named input with the exact value "babad".

Create two integer variables named start and maxLength initialized to 0 and 1 respectively.

Write a helper function expandAroundCenter that takes the string and two integer indices and returns the length of the palindrome expanding around those indices.

Use a for loop with variable i to iterate over the string indices and update start and maxLength to track the longest palindrome found.

Print the longest palindromic substring using fmt.Println.

💡 Why This Matters

🌍 Real World

Finding palindromes is useful in text analysis, DNA sequence research, and data validation.

💼 Career

Understanding string manipulation and algorithmic problem solving is essential for software development and coding interviews.

1

Create the input string

Create a string variable called input and set it to the exact value "babad".

DSA Go

# Create the input string variable 'input' with value "babad"
# Your code here

Hint

Use input := "babad" to create the string variable.

2

Add helper variables for tracking palindrome

Add two integer variables called start and maxLength initialized to 0 and 1 respectively inside the main function after input.

DSA Go

package main

import "fmt"

func main() {
    input := "babad"
    // Add variables start and maxLength
    // Your code here
}

Hint

Use start := 0 and maxLength := 1 to track the palindrome start and length.

3

Write the palindrome expansion helper function and core logic

Write a function called expandAroundCenter that takes a string s and two integers left and right, and returns the length of the palindrome expanding around those indices. Then, inside main, use a for loop with variable i from 0 to len(input)-1 to find the longest palindromic substring by calling expandAroundCenter twice for odd and even length palindromes. Update start and maxLength accordingly.

DSA Go

package main

import "fmt"

func expandAroundCenter(s string, left int, right int) int {
    // Your code here
}

func main() {
    input := "babad"
    start := 0
    maxLength := 1
    // Your code here
}

Hint

Use a loop to check palindromes centered at each index for odd and even lengths.

Update start and maxLength when a longer palindrome is found.

4

Print the longest palindromic substring

Print the longest palindromic substring from input using fmt.Println. Use slicing with start and maxLength to get the substring.

DSA Go

package main

import "fmt"

func expandAroundCenter(s string, left int, right int) int {
    for left >= 0 && right  len1 {
            length = len2
        }
        if length > maxLength {
            maxLength = length
            start = i - (length-1)/2
        }
    }
    // Print the longest palindromic substring
    // Your code here
}

Hint

Use fmt.Println(input[start : start+maxLength]) to print the substring.

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