Longest Palindromic Substring in c#

General
1

The Longest Palindromic Substring problem involves finding the longest substring within a given string that is a palindrome. A palindrome reads the same backward as forward (e.g., “racecar”).

Algorithm Explanation

A common approach to solve this problem efficiently is the “Expand Around Center” technique. Here’s how it works:

  1. Understanding Centers: A palindrome can be centered around a single character (odd-length palindromes) or between two characters (even-length palindromes). Therefore, for a string of length n, there are 2n - 1 possible centers.

  2. Expand Around Each Center:

    • For each center, expand outwards while the characters on both sides are the same.
    • Keep track of the longest palindrome found during this expansion.

  3. Return Result: After checking all possible centers, return the longest palindromic substring found.

C# Implementation

Here’s how you can implement this in C#:

using System;

class Program
{
    static void Main()
    {
        string input = "babad";
        string longestPalindrome = LongestPalindromicSubstring(input);
        Console.WriteLine("Longest Palindromic Substring: " + longestPalindrome);
    }

    static string LongestPalindromicSubstring(string s)
    {
        if (string.IsNullOrEmpty(s)) return "";

        string longest = "";
        
        for (int i = 0; i < s.Length; i++)
        {
            // Check for odd-length palindromes
            string oddPalindrome = ExpandAroundCenter(s, i, i);
            if (oddPalindrome.Length > longest.Length)
            {
                longest = oddPalindrome;
            }

            // Check for even-length palindromes
            string evenPalindrome = ExpandAroundCenter(s, i, i + 1);
            if (evenPalindrome.Length > longest.Length)
            {
                longest = evenPalindrome;
            }
        }

        return longest;
    }

    static string ExpandAroundCenter(string s, int left, int right)
    {
        while (left >= 0 && right < s.Length && s[left] == s[right])
        {
            left--;
            right++;
        }
        // Return the substring that is a palindrome
        return s.Substring(left + 1, right - left - 1);
    }
}

Explanation of Code

  1. Input: The program defines a string input that contains the text to analyze for palindromes.
  2. LongestPalindromicSubstring Function:
    • It initializes an empty string longest to keep track of the longest palindromic substring found.
    • A loop iterates over each character in the string, treating each index as a potential center for a palindrome.
    • For each index, it checks both odd-length and even-length palindromes by calling the ExpandAroundCenter method.
  3. ExpandAroundCenter Function:
    • This function takes the string and two indices (left and right) that represent the current center.
    • It expands outward while the characters at left and right are equal, effectively checking for palindromic conditions.
    • Once the expansion is complete, it returns the substring that represents the palindrome found.

Complexity

  • Time Complexity: O(n^2), where n is the length of the input string. This is due to the expansion around each character and checking up to n characters in the worst case.
  • Space Complexity: O(1), since we only use a few additional variables and the substring storage.

This approach is straightforward and effective for finding the longest palindromic substring, ensuring both clarity and efficiency.