Longest Palindromic Substring in DSA C#

Mental Model

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

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

s = "b a b a d"
indexes: 0 1 2 3 4
Check centers like:
  ↑
  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 letter is a palindrome of length 1

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

"b a" -> not palindrome

Why: Check even length palindromes by expanding around two centers

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

"a" -> palindrome length 1

Why: Single letter palindrome at index 1

Step 4: Expand palindrome around center index 1: "bab"

"b a b" -> palindrome length 3

Why: Expand left and right while characters match

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

"a b" -> not palindrome

Why: No even length palindrome here

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

"b" -> palindrome length 1

Why: Single letter palindrome at index 2

Step 7: Expand palindrome around center index 2: "aba"

"a b a" -> palindrome length 3

Why: Another palindrome of length 3 found

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

"a d" -> not palindrome

Why: No even length palindrome here

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

"a" -> palindrome length 1

Why: Single letter palindrome at index 3

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

"d" -> palindrome length 1

Why: Single letter palindrome at index 4

Result:

"bab" or "aba" -> longest palindromic substring length 3

Annotated Code

DSA C#

using System;

public class Solution {
    // Expand around center helper
    private static string ExpandAroundCenter(string s, int left, int right) {
        while (left >= 0 && right < s.Length && s[left] == s[right]) {
            left--;
            right++;
        }
        // Return substring after expanding
        return s.Substring(left + 1, right - left - 1);
    }

    public static string LongestPalindrome(string s) {
        if (string.IsNullOrEmpty(s)) return "";
        string longest = "";
        for (int i = 0; i < s.Length; i++) {
            // Odd length palindrome
            string odd = ExpandAroundCenter(s, i, i);
            if (odd.Length > longest.Length) {
                longest = odd;
            }
            // Even length palindrome
            string even = ExpandAroundCenter(s, i, i + 1);
            if (even.Length > longest.Length) {
                longest = even;
            }
        }
        return longest;
    }

    public static void Main() {
        string input = "babad";
        string result = LongestPalindrome(input);
        Console.WriteLine(result);
    }
}

while (left >= 0 && right < s.Length && s[left] == s[right]) { left--; right++; }

expand pointers outward while characters match to find palindrome

return s.Substring(left + 1, right - left - 1);

return the palindrome substring found after expansion

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

iterate over each character as potential palindrome center

string odd = ExpandAroundCenter(s, i, i);

check odd length palindrome centered at i

string even = ExpandAroundCenter(s, i, i + 1);

check even length palindrome centered between i and i+1

if (odd.Length > longest.Length) { longest = odd; }

update longest palindrome if odd palindrome is longer

if (even.Length > longest.Length) { longest = even; }

update longest palindrome if even palindrome is longer

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(n) for the substring storage in worst case when the entire string is a palindrome

vs Alternative: Brute force checks all substrings O(n^3), this center expansion reduces one loop making it O(n^2)

Edge Cases

empty string

returns empty string immediately

DSA C#

if (string.IsNullOrEmpty(s)) return "";

string with all same characters

returns the entire string as palindrome

DSA C#

while (left >= 0 && right < s.Length && s[left] == s[right])

string with no palindrome longer than 1

returns any single character

DSA C#

initial longest = "" and updates with single characters

When to Use This Pattern

When asked to find the longest palindrome substring, try expanding around each character as center to find palindromes efficiently.

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: Not updating longest palindrome correctly when a longer one is found
Fix: Compare lengths and update longest substring after each expansion

Summary

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

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

Check palindromes by expanding around each character and between characters to cover odd and even lengths.

Practice

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

easy

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

B. Count all palindromic substrings in the string

C. Reverse the entire string

D. Find the longest substring without repeating characters

Solution

1. Step 1: Understand the problem definition

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

2. Step 2: Differentiate from similar problems

   Counting all palindromic substrings or reversing the string are different tasks. The focus here is on the longest palindromic substring only.

3. Final Answer:

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

4. Quick Check:

   Longest palindromic substring = Find the longest substring that reads the same forwards and backwards [OK]

Hint: Look for substring that mirrors itself exactly [OK]

Common Mistakes:

• Confusing substring with subsequence
• Counting all palindromes instead of longest
• Trying to reverse entire string

2. Which of the following C# code snippets correctly initializes a 2D boolean array dp for dynamic programming in the Longest Palindromic Substring problem?

easy

A. bool dp = new bool[s.Length, s.Length];

B. bool[][] dp = new bool[s.Length][];

C. bool[,] dp = new bool[s.Length, s.Length];

D. bool dp[][] = new bool[s.Length][s.Length];

Solution

1. Step 1: Understand C# array syntax

   In C#, a 2D array is declared as type[,] name = new type[size1, size2];. bool[,] dp = new bool[s.Length, s.Length]; uses this correct syntax.

2. Step 2: Identify incorrect syntax

   bool[][] dp = new bool[s.Length][]; declares jagged arrays but misses initializing inner arrays. bool dp[][] = new bool[s.Length][s.Length]; uses invalid syntax for C#. bool dp = new bool[s.Length, s.Length]; tries to declare a single boolean variable with array sizes, which is invalid.

3. Final Answer:

   bool[,] dp = new bool[s.Length, s.Length]; -> Option C

4. Quick Check:

   2D array in C# = bool[,] dp = new bool[s.Length, s.Length]; [OK]

Hint: Use comma inside brackets for 2D arrays in C# [OK]

Common Mistakes:

• Using jagged array syntax without initializing inner arrays
• Confusing C# array syntax with other languages
• Declaring arrays without proper dimensions

3. What will be the output of the following C# code snippet that finds the longest palindromic substring?

string s = "babad";
string result = LongestPalindrome(s);
Console.WriteLine(result);

string LongestPalindrome(string str) {
    int start = 0, maxLength = 1;
    int len = str.Length;
    bool[,] dp = new bool[len, len];
    for (int i = 0; i < len; i++) dp[i, i] = true;
    for (int length = 2; length <= len; length++) {
        for (int i = 0; i <= len - length; i++) {
            int j = i + length - 1;
            if (str[i] == str[j]) {
                if (length == 2 || dp[i + 1, j - 1]) {
                    dp[i, j] = true;
                    if (length > maxLength) {
                        start = i;
                        maxLength = length;
                    }
                }
            }
        }
    }
    return str.Substring(start, maxLength);
}

medium

A. "aba"

B. "bab"

C. "bad"

D. "babad"

Solution

1. Step 1: Understand the input and algorithm

   The input string is "babad". The code uses dynamic programming to find the longest palindromic substring by checking substrings of increasing length.

2. Step 2: Trace the longest palindrome found

   Both "bab" and "aba" are palindromes of length 3. The code updates start and maxLength when it finds a longer palindrome. It finds "bab" first and returns it.

3. Final Answer:

   "bab" -> Option B

4. Quick Check:

   Longest palindrome in "babad" = "bab" [OK]

Hint: DP finds first longest palindrome substring [OK]

Common Mistakes:

• Assuming "aba" is returned instead of "bab"
• Returning entire string instead of substring
• Ignoring substring length updates

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

string LongestPalindrome(string s) {
    int n = s.Length;
    bool[,] dp = new bool[n, n];
    int maxLen = 1, start = 0;
    for (int i = 0; i < n; i++) dp[i, i] = true;
    for (int length = 2; length <= n; length++) {
        for (int i = 0; i < n - length; i++) {
            int j = i + length - 1;
            if (s[i] == s[j]) {
                if (length == 2 || dp[i + 1, j - 1]) {
                    dp[i, j] = true;
                    if (length > maxLen) {
                        start = i;
                        maxLen = length;
                    }
                }
            }
        }
    }
    return s.Substring(start, maxLen);
}

medium

A. The inner loop condition should be < i < n - length + 1

B. The substring method parameters are incorrect

C. The dp array is not initialized for single characters

D. The code does not check for palindrome substrings of length 1

Solution

1. Step 1: Analyze the inner loop boundary

   The inner loop runs with condition i < n - length. For substring length 'length', the last valid start index is n - length, but the loop only goes up to n - length - 1, missing it. The loop condition should be i <= n - length or equivalently i < n - length + 1 to include the last substring.

2. Step 2: Identify off-by-one error

   This is an off-by-one error in the inner loop condition. Other options are incorrect because the dp array is initialized for single characters, the substring parameters are correct, and length 1 substrings are handled.

3. Final Answer:

   The inner loop condition should be < i < n - length + 1 -> Option A

4. Quick Check:

   Loop boundary off-by-one = The inner loop condition should be < i < n - length + 1 [OK]

Hint: Check loop boundaries carefully for substring indices [OK]

Common Mistakes:

• Ignoring off-by-one errors in loops
• Misunderstanding substring parameters
• Assuming dp initialization is missing

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

hard

A. Expand Around Center approach; substring is "forgeeksskeegfor"

B. Dynamic Programming approach; substring is "forgeeksskeegfor"

C. Brute Force approach; substring is "forgeeksskeegfor"

D. Expand Around Center approach; substring is "geeksskeeg"

Solution

1. Step 1: Understand the input string and palindrome

   The string "forgeeksskeegfor" contains the palindrome "geeksskeeg" in the middle, which is the longest palindromic substring.

2. Step 2: Identify correct approach and substring

   The Expand Around Center approach efficiently finds palindromes by expanding from each center. It will find "geeksskeeg" correctly. The entire string is not a palindrome, so options B, C, and D are incorrect.

3. Final Answer:

   Expand Around Center approach; substring is "geeksskeeg" -> Option D

4. Quick Check:

   Longest palindrome = "geeksskeeg" via center expansion [OK]

Hint: Expand from centers to find longest palindrome fast [OK]

Common Mistakes:

• Assuming entire string is palindrome
• Confusing brute force with efficient methods
• Missing the correct longest substring