Tags

,

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

Solution 1: brute force way to do it would be scan each character in S, and compare its left and right, and until its left and right are not equal. that would be O(n^2).

        public string LongestPalindrome(string s)
        {
            var longest = 0;
            var start = -1;

            for (int i = 0; i < s.Length - longest / 2; i++)
            {                 
                // odd                 
                var gap = 1;                 
                while (i - gap >= 0 && i + gap < s.Length && s[i - gap] == s[i + gap])
                {
                    gap++;
                }

                if (longest < 1 + (gap - 1) * 2)
                {                     
                    longest = 1 + (gap - 1)*2;                     
                    start = i - gap + 1;                 
                }                                  
                // even                 
                gap = 0;                 
                while (i - gap >= 0 && i + 1 + gap < s.Length && s[i - gap] == s[i + 1 + gap])
                {
                    gap++;
                }

                if (longest < gap * 2)
                {                     
                    longest = gap*2;                     
                    start = i - gap + 1;                 
                }                 
                gap = 0;                 
                while (i - 1 - gap >= 0 && i + gap < s.Length && s[i - 1 - gap] == s[i + gap])
                {
                    gap++;
                }

                if (longest < gap * 2)
                {
                    longest = gap * 2;
                    start = i - gap - 1;
                }
            }

            return s.Substring(start, longest);
        }

Solution 2: dynamic programming, O(N^2) time and space complexity. dp[i, len] denotes if string start at i with length len is palindrome or not.

        public string LongestPalindrome(string s)
        {
            if (string.IsNullOrEmpty(s)) return String.Empty;
            var res = string.Empty;
            var reslen = 0;
            var dp = new bool[s.Length, s.Length];


            for (int len = 1; len <= s.Length; len++)
            {
                for (int i = 0; i + len <= s.Length; i++)
                {
                    dp[i, len] = (len - 2 <= 0 || dp[i + 1, len - 2]) && s[i] == s[i + len - 1];                     
                    if (dp[i, len] && len > reslen)
                    {
                        res = s.Substring(i, len);
                    }
                }
            }

            return res;
        }

Solution 3: we can use dynamic programming to solve it. assume that we know S from 0 to i has longest sub string length x. so how do we calculate the S from 0 to i+1’s longest sub string length? There are only two cases that the new added character (i+1) would become longest sub string,

  • character(i+1) combines the previous x to format new palindromic sub string with length x + 1; (this is odd case)
  • character(i+1) combines the previous x+ 1 to format new palindromic sub string with length x + 2; (this is even case)

since we know if we add a string to the existing string, the longest length it can add is 1 or 2. So the above two cases make scene.

        public String longestPalindrome(String s)
        {
            var resultStart = 0;
            var length = s.Length;
            var dp = new int[length];
            dp[0] = 1;

            for (var i = 1; i < length; i++)             
            {                 
                 var previous = dp[i - 1];                 
                 // check length + 2                 
                 if (IsPalindrome(s, i - previous - 1, i))
                 {                     
                      dp[i] = dp[i - 1] + 2;                     
                      resultStart = i - previous - 1;                
                 }                 
                 // check length + 1                 
                 else if (IsPalindrome(s, i - previous, i))          
                 {                     
                      dp[i] = dp[i - 1] + 1;                     
                      resultStart = i - previous;         
                 }                 
                 else
                 {                     
                      dp[i] = dp[i - 1];                 
                 }
             }             
             return s.Substring(resultStart, dp[length - 1]);
         }         
         private static bool IsPalindrome(string s, int start, int end)         
         {             
             while (start >= 0 && start < end && s[start] == s[end])
             {                 
                  start++;                 
                  end--;             
             }             
             return start >= end;
        }

Solution 4: set an odd and even center at i, then expand it with requirement of palindrome. Time complexity is O(n^2). space complexity is O(1).

        public string LongestPalindrome2(string s)
        {
            if (string.IsNullOrEmpty(s)) return String.Empty;
            var res = string.Empty;
            var reslen = 0;

            for (int i = 0; i < s.Length; i++)             
            {                 
                var p1 = expandAroundCenter(s, i, i);                 
                if (p1.Length > reslen)
                {
                    reslen = p1.Length;
                    res = p1;
                }

                var p2 = expandAroundCenter(s, i, i + 1);
                if (p2.Length > reslen)
                {
                    reslen = p2.Length;
                    res = p2;
                }
            }

            return res;
        }

        private string expandAroundCenter(string s, int i, int j)
        {
            while (i >= 0 && j < s.Length && s[i] == s[j])
            {
                i--;
                j++;
            }

            return s.Substring(i + 1, j - i - 1);
        }

Solution 5: Manacher’s algorithm, see this for more explanation.

    public string LongestPalindrome(string s) {
            var res = string.Empty;
            var reslen = 0;

            var swithpounds = preprocess(s);
            var maxR = 0;
            var maxC = 0;
            var dp = new int[swithpounds.Length];
            for (int i = 0; i < swithpounds.Length; i++)             
            {                 
                dp[i] = maxR > i ? Math.Min(dp[2 * maxC - i], maxR - i) : 0;

                // attempt to expand it
                while (i + 1 + dp[i] < swithpounds.Length && i - 1 - dp[i] >= 0 && swithpounds[i + 1 + dp[i]] == swithpounds[i - 1 - dp[i]])
                {
                    dp[i]++;
                }

                if (dp[i] + i > maxR)
                {
                    maxR = dp[i] + i;
                    maxC = i;
                }

                if (dp[i] > reslen)
                {
                    reslen = dp[i];
                    res = s.Substring((i - dp[i])/2, reslen);
                }
            }

            return res;
    }
    
        private string preprocess(string s)
        {
            var stringbuilder = new StringBuilder();
            foreach (char ch in s)
            {
                stringbuilder.Append("#");
                stringbuilder.Append(ch);
            }

            stringbuilder.Append("#");

            return stringbuilder.ToString();
        }
Advertisements