Longest Palindrome, by Amazon

Here is the Daily Coding Problem:

This problem was asked by Amazon.

Given a string, find the longest palindromic contiguous substring. If there are more than one with the maximum length, return any one.

For example, the longest palindromic substring of "aabcdcb" is "bcdcb". The longest palindromic substring of "bananas" is "anana".

There is an O(n^3) solution:

For i 0..n-1
  For j i..n-1
    Check whether substring(i,j) is a palindrome

Don't do it. There is a better O(n^2) solution, which is the one I'll implement in this post:

For i 0..n-1
  (1) Assume position i is the center of a palindrome
  (2) Move left and right from i while (1) is true

Ultimately, there is actually a linear solution to this problem: https://articles.leetcode.com/longest-palindromic-substring-part-ii/, however, this blog post is narrow enough to fit the solution. Jk, I don't get that solution.... Cheers, Boris.

GitHub: https://github.com/BorisVasilenko/dailycodingproblem/blob/master/DailyCodingProblem10302018.cs

Code:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace DailyCodingProblem
{
 class DailyCodingProblem10302018
 {
  public string LongestPalindrome(string str)
  {
   if (String.IsNullOrEmpty(str)) return str;

   string longest = "";
   for (int i = 0; i < str.Length; i++)
   {
    //Odd
    int l = i;
    int r = i;
    string current = "";
    while (l >= 0 && r < str.Length)
    {
     if (str[l] != str[r]) break;
     if (l == r) current += str[l].ToString();
     else current = str[l].ToString() + current + str[r].ToString();
     l--;
     r++;
    }
    if (current.Length > longest.Length) longest = current;

    //Even
    l = i;
    r = i + 1;
    current = "";
    while (l >= 0 && r < str.Length)
    {
     if (str[l] != str[r]) break;
     if (l == r) current += str[l].ToString();
     else current = str[l].ToString() + current + str[r].ToString();
     l--;
     r++;
    }
    if (current.Length > longest.Length) longest = current;
   }

   return longest;
  }
 }
}