Longest Palindromic Substring

Longest Palindromic Substring

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.

Example

Given the string = `"abcdzdcab"`, return `"cdzdc"`.

Challenge

O(n2) time is acceptable. Can you do it in O(n) time.

Solution1. DP O(n^2)

P[i,j] = 字符串区间[i,j]是否为palindrome.

S=    a  b  c  c  b
Index = 0  1  2  3  4

P[0,0] =1  //each char is a palindrome
P[0,1] =S[0] == S[1]    , P[1,1] =1
P[0,2] = S[0] == S[2] && P[1,1], P[1,2] = S[1] == S[2] , P[2,2] = 1
P[0,3] = S[0] == S[3] && P[1,2], P[1,3] = S[1] == S[3] && P[2,2] , P[2,3] =S[2] ==S[3],  P[3,3]=1
………………….

P[i,j] = 1  if i ==j
=  S[i] ==S[j]   if j = i+1
=  S[i] == S[j] && P[i+1][j-1]  if j>i+1

```public String longestPalindrome(String s) {
if (s == null) {
return "";
}
String res = "";
int n = s.length();
boolean[][] dp = new boolean[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j <= i; j++) {
if (i - j <= 2) {
dp[j][i] = s.charAt(i) == s.charAt(j);
} else {
dp[j][i] = s.charAt(i) == s.charAt(j) && dp[j + 1][i - 1];
}
if (dp[j][i]) {
if (i - j + 1 > res.length()) {
res = s.substring(j, i + 1);
}
}
}
}
return res;
}```

Solution2: Check both aba and abba 2 cases. O(n^2)

```public String longestPalindrome(String s) {
if (s == null || s.length() == 0) {
return "";
}
String result = "";

//1. if it is like 'aba'
for (int i = 0; i < s.length(); i++) {
int count = 0;
while (i - count >= 0 && i + count < s.length() && s.charAt(i - count) == s.charAt(i + count)) {
count++;
}
String palindrome = s.substring(i - count + 1, i + count);
if (palindrome.length() > result.length()) {
result = palindrome;
}
}

//2. if it is like 'abba', the pivot would be the interval between i and i+1
for (int i = 0; i < s.length() - 1; i++) {
int count = 1;
while (i - count + 1 >= 0 && i + count < s.length() && s.charAt(i - count + 1) == s.charAt(i + count)) {
count++;
}
if (count > 1) {
String palindrome = s.substring(i - count + 2, i + count);
if (palindrome.length() > result.length()) {
result = palindrome;
}
}
}

return result;
}```

Share

Longest Common Prefix

Longest Common Prefix

Given k strings, find the longest common prefix (LCP).

Example

For strings `"ABCD"`, `"ABEF"` and `"ACEF"`, the LCP is `"A"`

For strings `"ABCDEFG"`, `"ABCEFG"` and `"ABCEFA"`, the LCP is `"ABC"`

```public String longestCommonPrefix(String[] strs) {
if (strs == null || strs.length == 0) {
return "";
}
String lcp = strs[0];
for (int i = 1; i < strs.length; i++) {
lcp = getLCP(lcp, strs[i]);
}
return lcp;
}

public String getLCP(String s1, String s2) {
StringBuilder sb = new StringBuilder();
int n = Math.min(s1.length(), s2. length());
for (int i = 0; i < n; i++) {
if (s1.charAt(i) == s2.charAt(i)) {
sb.append(s1.charAt(i));
} else {
break;
}
}
return sb.toString();
}```