O(n^2) iterative solution with constant space complexity, any further optimizations possible ?


  • 0
    V

    In this version of program, it keeps track of maximum length palindrome of both odd and even lengths' and towards the end it returns the longest length palindrome if one exists.

    In the first "while" loop even length palindromes are generated by first fixing two centers and expanding in both forward and backward directions

    NOTE:Inside the first "while"loop indices i and i-1 are chosen as centers, i and i+1 can also be chosen as centers

    In the second "while" loop odd length palindromes are generated by fixing a center and expanding in both forward and backward directions

      class Solution {
        public:
            string longestPalindrome(string s) {
          
        int start = 0;
         int maxLength = 1; 
        string res;
           
            if(s.length()==1)
               return s;
            int low, high;
            for (int i = 1; i < s.length(); ++i)
            {
                low = i - 1;
                high = i;
                while (low >= 0 && high < s.length() && s[low] == s[high])
                {
                    if (high - low + 1 > maxLength)
                    {
                        start = low;
                        maxLength = high - low + 1;
                    }
                    --low;
                    ++high;
                }
                 low = i - 1;
                high = i + 1;
                while (low >= 0 && high <s.length() && s[low] == s[high])
                {
                    if (high - low + 1 > maxLength)
                    {
                        start = low;
                        maxLength = high - low + 1;
                    }
                    --low;
                    ++high;
                }
            }
             res = s.substr(start,maxLength);
        return res;            
        
            
        }
        };

  • 1
    F

    Manacher's Algorithm takes linear time.


  • 0
    V

    O(n) Solution using manacher's algorithm

    public class Solution {
        
            public static String longestPalindrome(String s) {
            if (s==null || s.length()==0)
              return "";
         
            char[] s2 = addBoundaries(s.toCharArray());
            int[] p = new int[s2.length]; 
            int c = 0, r = 0; // Here the first element in s2 has been processed.
            int m = 0, n = 0; // The walking indices to compare if two elements are the same
            for (int i = 1; i<s2.length; i++) {
              if (i>r) {
                p[i] = 0; m = i-1; n = i+1;
              } else {
                int i2 = c*2-i;
                if (p[i2]<(r-i)) {
                  p[i] = p[i2];
                  m = -1; // This signals bypassing the while loop below. 
                } else {
                  p[i] = r-i;
                  n = r+1; m = i*2-n;
                }
              }
              while (m>=0 && n<s2.length && s2[m]==s2[n]) {
                p[i]++; m--; n++;
              }
              if ((i+p[i])>r) {
                c = i; r = i+p[i];
              }
            }
            int len = 0; c = 0;
            for (int i = 1; i<s2.length; i++) {
              if (len<p[i]) {
                len = p[i]; c = i;
              }
            }
            char[] ss = Arrays.copyOfRange(s2, c-len, c+len+1);
            return String.valueOf(removeBoundaries(ss));
          }
         
          private static char[] addBoundaries(char[] cs) {
            if (cs==null || cs.length==0)
              return "||".toCharArray();
         
            char[] cs2 = new char[cs.length*2+1];
            for (int i = 0; i<(cs2.length-1); i = i+2) {
              cs2[i] = '|';
              cs2[i+1] = cs[i/2];
            }
            cs2[cs2.length-1] = '|';
            return cs2;
          }
         
          private static char[] removeBoundaries(char[] cs) {
            if (cs==null || cs.length<3)
              return "".toCharArray();
         
            char[] cs2 = new char[(cs.length-1)/2];
            for (int i = 0; i<cs2.length; i++) {
              cs2[i] = cs[i*2+1];
            }
            return cs2;
          }    
        }
    

    reference Manacher's Agorithm


  • 0
    L

    My idea is same with yours, a little improvement, you can only check the max length when the while is end.

    public class Solution
    {
        public String longestPalindrome(String s)
        {
            if (s == null)
            {
                return null;
            }
            else if (s.length() <= 1)
            {
                return s;
            }
            
            int max = 1;
            String result = s.substring(0, 1);
            
            for (int i = 0; i < s.length(); ++i)
            {
                int j;
                for (j = 1; i - j >= 0 && i + j - 1 < s.length() && s.charAt(i - j) == s.charAt(i + j - 1); ++j)
                {
                }
                
                --j;
                if (2 * j > max)
                {
                    max = 2 * j;
                    result = s.substring(i - j, i + j);
                }
                
                for (j = 1; i - j >= 0 && i + j < s.length() && s.charAt(i - j) == s.charAt(i + j); ++j)
                {
                    
                }
                
                --j;
                
                if (2 * j + 1 > max)
                {
                    max = 2 * j + 1;
                    result = s.substring(i - j, i + j + 1);
                }
            }
            
            return result;
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.