Longest Palindromic Substring medium

Problem Statement

Given a string s, find the longest palindromic substring in s.

Example 1

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

Example 2

Input: s = "cbbd"
Output: "bb"

Steps and Explanation

This problem can be solved using dynamic programming or a more efficient approach based on expanding around the center. We'll use the latter for its improved time complexity.

The core idea is that a palindrome can be centered around either a single character or a pair of identical characters. We iterate through each character (and each pair of adjacent characters) as a potential center and expand outwards to find the longest palindrome centered there.

1. Initialization: Create a variable maxLen to store the length of the longest palindrome found so far, and start to store the starting index of that palindrome.

2. Iteration: Iterate through the string:

   • For each character i, consider it as a potential center of a palindrome (odd length). Expand outwards from i checking for symmetry (s[i-k] == s[i+k]).
   • For each pair of adjacent characters i and i+1, consider them as a potential center of a palindrome (even length). Expand outwards from i and i+1 checking for symmetry (s[i-k] == s[i+k+1]).

3. Expansion: In both cases (odd and even length), expand as long as the characters at the symmetric positions are equal. Update maxLen and start if a longer palindrome is found.

4. Return: After iterating through the entire string, return the substring s.Substring(start, maxLen).

Code (C#)

public class Solution {
    public string LongestPalindrome(string s) {
        int n = s.Length;
        if (n < 2) {
            return s;
        }

        int start = 0;
        int maxLen = 1;

        for (int i = 0; i < n; i++) {
            // Odd length palindrome
            int l = i, r = i;
            while (l >= 0 && r < n && s[l] == s[r]) {
                if (r - l + 1 > maxLen) {
                    start = l;
                    maxLen = r - l + 1;
                }
                l--;
                r++;
            }

            // Even length palindrome
            l = i;
            r = i + 1;
            while (l >= 0 && r < n && s[l] == s[r]) {
                if (r - l + 1 > maxLen) {
                    start = l;
                    maxLen = r - l + 1;
                }
                l--;
                r++;
            }
        }

        return s.Substring(start, maxLen);
    }
}

Complexity

• Time Complexity: O(n^2), where n is the length of the string. This is because we might have to expand outwards from each of the n possible centers, and in the worst case, the expansion can take O(n) time.

• Space Complexity: O(1). The algorithm uses a constant amount of extra space. We only store a few variables (start, maxLen, l, r).