005.Longest Palindromic substring

Posted on | In

Solution 1��? time limit exceeded

Time: O(n^2), Space: O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() < 2)
            return s;
            
        String output = "";
        
        for (int i = 0; i < s.length(); i++) {
           for (int j = 0; j < i + 1; j++) {
               int start = j;
               int end = i;
               while (s.charAt(start) == s.charAt(end)) {
                   if (end - start == 2 || end - start == 1) {
                        output = output.length() >= s.substring(j,i + 1).length()? output: s.substring(j,i + 1);
                        break;
                   }
                   if (end == 0 || start == i)
                       break;
                   start++;
                   end--;
               }
           }
        }
    return output;
    }
}

Mutation: Replacing string manipulation with int values, but it dones’t improve the performance.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public class Solution {
    public String longestPalindrome(String s) {
        
        int length = s.length();
        int startLocation = 0;
        int longestLength = 0;
        if (s == null || length < 2)
            return s;
        
        for (int i = 0; i < length; i++) {
           for (int j = 0; j < i + 1; j++) {
               int start = j;
               int end = i;
               while (s.charAt(start) == s.charAt(end)) {
                   if (end - start == 2 || end - start == 1) {
                        if (longestLength < i - j + 1) {
                            startLocation = j;
                            longestLength = i - j + 1;
                        }
                        break;
                   }
                   if (end == 0 || start == i)
                       break;
                   start++;
                   end--;
               }
           }
        }
    return s.substring(startLocation, startLocation + longestLength);
    }
}

Solution 2: accepted, 37%

中间��?��?

Time: O(2 n^2), Space: O(1)
avoid unnecessary check, but still O(n^2), failed the “aaaaaaaa…” test case.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public static String longestPalindrome(String s) {
	if (s == null || s.length() < 2) return s;
    	int len = s.length();
    	int start = 0;
    	int max = 0;
        for(int i = 0; i < len; i++) { 
        	// break if it's not possible to find longer output
        	if (len - i < max / 2)
        		break;
        	
        	// for "aba"
        	int left = i;
        	int right = i;
        	while (left >= 0 && right < len && s.charAt(left) == s.charAt(right)) {
        		left--;
        		right++;
        	}
        	if (right - left - 2 >= max) {
        		max = right - left - 2;
        		start = left + 1;
        	}    	
        	
        	// for "abba"
        	left = i;
        	right = i + 1;
        	while (left >= 0 && right < len && s.charAt(left) == s.charAt(right)) {
        		left--;
        		right++;
        	}
        	if (right - left - 2 >= max) {
        		max = right - left - 2;
        		start = left + 1;
        	}    	
        }        
        return s.substring(start, start + max + 1);
}

We should be able to cut the time to half by check “aba” and “abba” in the same loop:

Solution 3: accepted, 99%

Amaing boost in performace simply because I changed the duplicated code block in solution 2 to method. Is this the truth?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class Solution {
    private int start, max;
    public String longestPalindrome(String s) {
        if (s == null || s.length() < 2) return s;
    	int len = s.length();
        for(int i = 0; i < len; i++) { 
        	// break if it's not possible to find longer output
        	if (len - i < max / 2)
        		break;
        	extendPalindrome(s, i, i);
        	extendPalindrome(s, i, i + 1);
        }        
        return s.substring(start, start + max);
    }
    private void extendPalindrome(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
    		left--;
    		right++;
    	}
    	if (max < right - left - 1) {
    		start = left + 1;
    		max = right - left - 1;
    	}
    }
}

Test case 1

Solution 1: ~100ms
Solution 2: ~6ms (without “len - i < output.length() / 2” it will be 10ms and will not be accepted)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
System.out.println(longestPalindrome("") + "/");
System.out.println(longestPalindrome("a") + "/a");
System.out.println(longestPalindrome("aa") + "/aa");
System.out.println(longestPalindrome("aaa") + "/aaa");
System.out.println(longestPalindrome("abc") + "/a");
System.out.println(longestPalindrome("aabaa") + "/aabaa");
System.out.println(longestPalindrome("ababababa") + "/ababababa");
System.out.println(longestPalindrome("kaba") + "/aba");
System.out.println(longestPalindrome("abak") + "/aba");
System.out.println(longestPalindrome("kabad") + "/aba");
System.out.println(longestPalindrome("kabba") + "/abba");
System.out.println(longestPalindrome("kabbad") + "/abba");
System.out.println(longestPalindrome("aaaakabbad") + "/aaaa");
System.out.println(longestPalindrome("kabbadaaaa") + "/abba");
System.out.println(longestPalindrome("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"));