Given a string s, the goal is to locate the longest cnotiguous sequence of characters that reads identically forward and backward. The input string length is capped at 1000 characters.

Problem Examples

Example 1:

• Input: "babad"
• Output: "bab"
• Note: "aba" is also a valid solution.

Example 2:

• Input: "cbbd"
• Output: "bb"

Optimal Implementation: Center Expasnion

A palindrome is symmetric. We can leverage this property by iterating through the string and considering each position (and the space between positions) as a potential center. By expanding outward from these centers, we can find the boundaries of all palindromic substrings.

public class PalindromeSolver {
    public string FindLongest(string text) {
        if (string.IsNullOrEmpty(text)) return string.Empty;

        int start = 0, end = 0;
        for (int i = 0; i < text.Length; i++) {
            // Case 1: Palindrome with an odd length (e.g., "aba")
            int lenOdd = ExpandFromMiddle(text, i, i);
            // Case 2: Palindrome with an even length (e.g., "bb")
            int lenEven = ExpandFromMiddle(text, i, i + 1);

            int currentMax = Math.Max(lenOdd, lenEven);
            if (currentMax > end - start) {
                start = i - (currentMax - 1) / 2;
                end = i + currentMax / 2;
            }
        }

        return text.Substring(start, end - start + 1);
    }

    private int ExpandFromMiddle(string s, int left, int right) {
        while (left >= 0 && right < s.Length && s[left] == s[right]) {
            left--;
            right++;
        }
        // Return the length of the found palindrome
        return right - left - 1;
    }
}

Complexity Analysis

• Time Complexity: O(n²). We visit each of the 2n-1 possible centers and perform an expansion that takes up to O(n) time.
• Space Compleixty: O(1). This approach uses a constant amount of additional space regardless of the input size, as we only store indices.