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.
O( n^2 ) time O(1) space solution 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 public class Solution { public String longestPalindrome (String s) { if (s.length() < 2 ) return s; int start = 0 , maxLength = 1 ; for (int i = 0 ; i < s.length();){ if (s.length() - i <= maxLength / 2 ) break ; int j = i, k = i; while (k < s.length() - 1 && s.charAt(k + 1 ) == s.charAt(k)){k++;} i = k + 1 ; while (k < s.length() - 1 && j > 0 && s.charAt(k + 1 ) == s.charAt(j - 1 )){ k++; j--; } if (maxLength < k - j + 1 ){ start = j; maxLength = k - j + 1 ; } } return s.substring(start, start + maxLength); } }
O( n ^2 ) time O( n^2 ) space DP solution, can be optimized to O(n) space 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 public class Solution { public String longestPalindrome (String s) { if (s == null ) return s; int start = 0 , length = 0 ; boolean [][] dp = new boolean [s.length()][s.length()]; for (int left = s.length() - 1 ; left >= 0 ; left--) { for (int right = left; right < s.length(); right++) { dp[left][right] = s.charAt(left) == s.charAt(right) && (right - left < 3 || dp[left + 1 ][right - 1 ]); if (dp[left][right] && right - left + 1 > length) { start = left; length = right - left + 1 ; } } } return s.substring(start, start + length); } }
O(n) time Manacher’s Algorithm https://www.felix021.com/blog/read.php?2040