O(n) using idea similar to LPS (~358 msec)


  • 0
    V

    Using idea similar to expanding from centers like in Longest palindromic substring.
    For a string such as "aacecaaa", start expanding with centers from mid to 0 (no need to include mid, mid+1 as center for odd length string).

    The first center that reaches -1 on the left on expanding will give the shortest palindrome.
    In above case, it will be center "e" "e". Take the substring from the index at which expansion ended on the right, reverse it and pre-pend to original string to obtain shortest palindrome.
    In above case, "a" + "aacecaaa".

    public String shortestPalindrome(String s) {
            int mid = s.length()/2;
            
            int[] res = expand(s, mid, mid);
            if (res[0] == -1)
            {
                if ((s.length() % 2) == 0)
                {
                    return (new StringBuilder(s.substring(res[1]))).reverse().toString() + s;
                }
                else
                {
                    return s;
                }
            }
            
            // for even length string, check n/2 n/2+1 also as center for expansion
            if ((s.length() % 2) == 0)
            {
                if (expand(s, mid, mid+1)[0] == -1)
                {
                    return s;
                }
            }
    
            for (int i=mid-1; i>=0; i--)
            {
                int[] res1 = expand(s, i, i+1);
                if (res1[0] == -1)
                {
                    return (new StringBuilder(s.substring(res1[1]))).reverse().toString() + s;
                }
                
                int[] res2 = expand(s, i, i);
                if (res2[0] == -1)
                {
                    return (new StringBuilder(s.substring(res2[1]))).reverse().toString() + s;
                }
            }
            
            return "";
        }
        
        public int[] expand(String s, int left, int right)
        {
            while(left>=0 && right<s.length() && (s.charAt(left) == s.charAt(right)))
            {
                left--;
                right++;
            }
            
            int result[] = {left, right};
            return result;
        }

  • 0
    A

    Thanks for the solution.
    Why run time complexity is O(n)? expand function is O(n) within the loop which is running n/2 times. So time complexity should be O(n^2). Please correct me if I am wrong.


  • 0
    A

    @astha6 Yes it is

    cleaner code will be :

    public String shortestPalindrome(String s) {
        int mid = s.length()/2;
        
        for (int i=mid; i>=0; i--)
        {
            int[] res1 = expand(s, i, i+1);
            if (res1[0] == -1)
            {
                return (new StringBuilder(s.substring(res1[1]))).reverse().toString() + s;
            }
            
            int[] res2 = expand(s, i, i);
            if (res2[0] == -1)
            {
                return (new StringBuilder(s.substring(res2[1]))).reverse().toString() + s;
            }
        }
        
        return "";
    }
    
    public int[] expand(String s, int left, int right)
    {
        while(left>=0 && right<s.length() && (s.charAt(left) == s.charAt(right)))
        {
            left--;
            right++;
        }
        
        int result[] = {left, right};
        return result;
    }

Log in to reply
 

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