using System;

public class Program

{

    public static void Main()

    {

        //TestLongestPalindrome("babad", "bab");

        TestLongestPalindrome("cbbd", "bb");

        //TestLongestPalindrome("bb", "bb");

        //TestLongestPalindrome("abcba", "abcba");

        //TestLongestPalindrome("a", "a");

    }

    public static void TestLongestPalindrome(string s, string expected)

    {

        var actual = LongestPalindrome(s);

        Console.WriteLine($"{s} --> {actual}        expected: {expected}");

    }

    public static string LongestPalindrome(string s) {

        if(s.Length == 1){

            return s;

        }

​

        int maxLength = 0;

        string longestPalindrome = "";

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

            //Event case: i and i+1;

            Console.WriteLine($"Begin EVEN i: {i}");

            int MaxLengthEven = FindLongestPalindromeWithCenter(i, i+1,s);

            //Odd case: i

            Console.WriteLine($"Begin ODD i: {i}");

            int MaxLengthOdd = FindLongestPalindromeWithCenter(i,i,s);

​

            int currentMax = Math.Max(MaxLengthEven,MaxLengthOdd);

            //Console.WriteLine($"MaxLengthEven: {MaxLengthEven}, MaxLengthOdd: {MaxLengthOdd}");

​

            if(currentMax > maxLength){

                maxLength = currentMax;

                // 0 - (3-1)/2 = -1

                // 0 - (1-1)/2 = 0

​

                // babad

                var startIndex = i - (currentMax-1)/2;

                //Console.WriteLine($"i: {i}, currentMax: {currentMax}, startIndex: {startIndex}");

                longestPalindrome = s.Substring(startIndex,currentMax);

                //Console.WriteLine($"longestPalindrome: {longestPalindrome}");

            }

        }

​

        return longestPalindrome;

    }

​

    public static int FindLongestPalindromeWithCenter(int left, int right, string s){

​

        // Check if right is out of range OR if left & right chars don't match, if so return 0

        if (right >= s.Length || s[left] != s[right])

            return 0;

​

        Console.WriteLine($"Left: {s[left]}, Right: {s[right]}");

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

            left--;

            right++;

        }

        //abcba

        //Console.WriteLine($"correct: {right-left-1}");

        //Console.WriteLine($"Length: {right}-{left}+1 = {right-left+1}");

        return right-left+1;

    }

}