Palindrome - How to Succeed in Algorithms Interview
Palindrome
- O(N^2) DP or DFS+cache
- DFS + cache: easier to write
- or DP: use len
int[][] palindromeLen, boolean[][] isPalindrome; int j = i + len (- 1);
- expand at center expansion
- freqMap
- build palindrome
- Case: odd or ven length
- reverse
DP
- LeetCode 516 - Longest Palindromic Subsequence
- Minimum insertions to form a palindrome
- minInsertions(str[l+1…..h-1]) if str[l] is equal to str[h] otherwise min(minInsertions(str[l…..h-1]), minInsertions(str[l+1…..h])) + 1
- LeetCode 131 - Palindrome Partitioning: Return all possible palindrome partitioning of s
- O(2^N)(Xn)
- dfs + for loop from startIndex to end
- DP + cache/use previous results
public static List<List<String>> partition(String s) {
int len = s.length();
List<List<String>>[] result = new List[len + 1];
result[0] = new ArrayList<List<String>>();
result[0].add(new ArrayList<String>());
boolean[][] pair = new boolean[len][len];
for (int i = 0; i < s.length(); i++) {
result[i + 1] = new ArrayList<List<String>>();
for (int left = 0; left <= i; left++) {
if (s.charAt(left) == s.charAt(i) && (i - left <= 1 || pair[left + 1][i - 1])) {
pair[left][i] = true;
String str = s.substring(left, i + 1);
for (List<String> r : result[left]) {
List<String> ri = new ArrayList<String>(r);
ri.add(str);
result[i + 1].add(ri);
}
}
}
}
return result[len];
}
public List<List<String>> partition(String s) {
List<List<String>> res = new ArrayList<>();
if (s == null || s.isEmpty()) return res;
List<String> first = new ArrayList<>();
first.add(s.charAt(0) + "");
res.add(first);
for (int i = 1; i < s.length(); i++) {
String ch = s.charAt(i) + "";
int count = res.size();
for (int j = 0; j < count; j++) {
List<String> l = res.get(j);
int last = l.size() - 1;
if (l.get(last).equals(ch)) {
List<String> l2 = new ArrayList<>(l);
l2.add(l2.remove(last) + ch);
res.add(l2);
}
if (last > 0 && l.get(last - 1).equals(ch)) {
List<String> l2 = new ArrayList<>(l);
l2.add(l2.remove(last - 1) + l2.remove(last - 1) + ch);
res.add(l2);
}
l.add(ch);
}
}
return res;
}
- Find minimum number of insertion (or deletions) required to make it a palindrome
minimum inserts:
I[i..j] = I[i+1..j-1], if S[i] = S[j]
I[i..j] = min{I[i..j-1], I[i+1..j]}+1, otherwise.
Base Case :
I[i,i] = 0, as a single character itself is a palindrome.
L[k][j] = str.charAt(k) == str.charAt(j) ? L[k + 1][j - 1] : Math.min(L[k][j - 1], L[k + 1][j]) + 1;
Minimum deletes
d[i..j] = d[i+1..j-1], if d[i] = d[j] (i.e. no deletions required)
d[i..j] = min{d[i..j-1], d[i-1..j]}+1, otherwise. (i.e. one deletion required)
Base Case :
d[i,i] = i
d[0,j] = j
Expand at Center
OPT(i,j) = 2 + OPT(i+1, j-1) if A[i] = A[j],
= max (OPT(i,j-1), OPT(i+1,j), otherwise.
private int lo, maxLen;
public String longestPalindrome(String s) {
int len = s.length();
if (len < 2)
return s;
for (int i = 0; i < len-1; i++) {
extendPalindrome(s, i, i); //assume odd length, try to extend Palindrome as possible
extendPalindrome(s, i, i+1); //assume even length.
}
return s.substring(lo, lo + maxLen);
}
private void extendPalindrome(String s, int j, int k) {
while (j >= 0 && k < s.length() && s.charAt(j) == s.charAt(k)) {
j--;
k++;
}
if (maxLen < k - j - 1) {
lo = j + 1;
maxLen = k - j - 1;
}
}
public int minCut(String s) {
char[] c = s.toCharArray();
int n = c.length;
int[] cut = new int[n];
boolean[][] pal = new boolean[n][n];
for(int i = 0; i < n; i++) {
int min = i;
for(int j = 0; j <= i; j++) {
if(c[j] == c[i] && (j + 1 > i - 1 || pal[j + 1][i - 1])) {
pal[j][i] = true;
min = j == 0 ? 0 : Math.min(min, cut[j - 1] + 1);
}
}
cut[i] = min;
}
return cut[n - 1];
}
public int minCut(String s) {
if(s==null || s.length()<2){
return 0;
}
int n = s.length();
char[] t = s.toCharArray();
int[] dp = new int[n+1];
Arrays.fill(dp,Integer.MAX_VALUE);
dp[0] = -1;
int i = 0;
while(i<n){
expand(t,dp,i,i);
expand(t,dp,i,i+1);
i++;
}
return dp[n];
}
private void expand(char[] t,int[] dp,int i,int j){
while(i>=0 && j<t.length && t[i] == t[j]){
dp[j+1] = Math.min(dp[j+1],dp[i] + 1);
i--;j++;
}
}
Build Palindrome
freqMap
public int check(String str) {
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
for (int i=0; i<str.length(); i++) {
char c = str.charAt(i);
if (map.containsKey(c)) {
map.put(c, map.get(c)+1);
}
else {
map.put(c, 1);
}
}
int cntOdd = 0;
for (int val : map.values()) {
if (val % 2 == 1) {
cntOdd++;
}
}
return cntOdd>1? 0 : 1;
}
Two Pointers
public int countChunk(String str) {
if (str==null || str.length()==0) return 0;
int sum = 0;
int l=0, r=str.length()-1;
int preL = l, preR = r;
while (l < r) {
String left = str.substring(preL, l+1);
String right = str.substring(r, preR+1);
if (left.equals(right)) {
preL = l+1;
preR = r-1;
sum += 2;
}
l++;
r--;
}
if (preL <= preR) sum+=1;
return sum;
}
Reverse
Build Palindrome
Examples
