Palindrome
- O(N^2) DP or DFS+cache
- int[][] palindromeLen, boolean[][] isPalindrome
- DFS + cache: easier to write
- or DP: use len
int j = i + len (- 1);
- expand at center expansion
- freqMap
- edit distance of s and reverse of s
- longest common string of s and reverse of s
- edit distance of s and reverse of s
- longest common string of s and reverse of s
- O(N) two pointers
- reverse of string s
- methods:
Character.isAlphabetic/isDigit
LeetCode 516 - Longest Palindromic Subsequence
"bbbab" => 4
- brute force DFS
- brute force DFS + Memoization (time complexity same as its DP version)
- DP
OPT(i,j) = 2 + OPT(i+1, j-1) if A[i] = A[j], = max (OPT(i,j-1), OPT(i+1,j), otherwise.
for(int len = 2; len <= n; len++){ //try to get a palindrom of length len starting at each position i for(int i = 1; i <= n-len+1; i++){ //right end position of current palindrom int j = i+len-1; if(str.charAt(i-1) == str.charAt(j-1)){ dp[i][j] = 2+dp[i+1][j-1]; } else{ dp[i][j] = Math.max(dp[i][j-1], dp[i+1][j]); } } }
- TODO: Manacher’s Algorithm
Lexicographically first palindromic string
LeetCode - 409 Longest Palindrome
find the length of the longest palindromes that can be built with those letters.
- freqMap n - odds + 1
LeetCode 132 - Palindrome Partitioning II
Return the minimum cuts needed for a palindrome partitioning of s.
- isPalindrome[i][j] store if s[i..j] is palindrome or not. res[j] is the min cut of s[0..j]
Find all possible palindromic substrings in a string
Count All Palindrome Sub-Strings in a String
- expand at center expansion
Chunked Palindrome
- O(N) two pointers
7 int l=0, r=str.length()-1; 8 int preL = l, preR = r; 9 while (l < r) { 10 String left = str.substring(preL, l+1); 11 String right = str.substring(r, preR+1); 12 if (left.equals(right)) { 13 preL = l+1; 14 preR = r-1; 15 sum += 2; 16 } 17 l++; 18 r--; 19 } 20 if (preL <= preR) sum+=1;
Find if string is K-Palindrome or not
A k-palindrome string transforms into a palindrome on removing at most k characters from it
- edit distance of s and reverse of s <= 2k deletions
for
(
int
i = 0; i <= m; i++)
{
for
(
int
j = 0; j <= n; j++)
{
// If first string is empty, only option is to
// remove all characters of second string
if
(i == 0)
dp[i][j] = j;
// Min. operations = j
// If second string is empty, only option is to
// remove all characters of first string
else
if
(j == 0)
dp[i][j] = i;
// Min. operations = i
// If last characters are same, ignore last character
// and recur for remaining string
else
if
(str1[i - 1] == str2[j - 1])
dp[i][j] = dp[i - 1][j - 1];
// If last character are different, remove it
// and find minimum
else
dp[i][j] = 1 + min(dp[i - 1][j],
// Remove from str1
dp[i][j - 1]);
// Remove from str2
}
}
- longest common string of s and reverse of s
Find minimum number of merge operations (two adjacent elements) to make an array palindrome
- O(N) two pointers
for
(
int
i=
0
,j=n-
1
; i<=j;)
{
// If corner elements are same,
// problem reduces arr[i+1..j-1]
if
(arr[i] == arr[j])
{
i++;
j--;
}
// If left element is greater, then
// we merge right two elements
else
if
(arr[i] > arr[j])
{
// need to merge from tail.
j--;
arr[j] += arr[j+
1
] ;
ans++;
}
// Else we merge left two elements
else
{
i++;
arr[i] += arr[i-
1
];
ans++;
}
}
TODO 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- edit distance of s and reverse of s
- longest common string of s and reverse of s
LeetCode 214 - Shortest Palindrome
https://leetcode.com/problems/shortest-palindrome/
https://discuss.leetcode.com/topic/27261/clean-kmp-solution-with-super-detailed-explanation
LeetCode [267] Palindrome Permutation II
Given a string s, return all the palindromic permutations (without duplicates) of it. Return an empty list if no palindromic permutation could be form.
https://discuss.leetcode.com/topic/30850/java-6ms-solution-no-reversal-or-concat
https://discuss.leetcode.com/topic/22214/ac-java-solution-with-explanation
https://leetcode.com/problems/shortest-palindrome/
Given a string S, you are allowed to convert it to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can find by performing this transformation.
https://discuss.leetcode.com/topic/25860/my-9-lines-three-pointers-java-solution-with-explanationpublic String shortestPalindrome(String s) {
int i = 0, end = s.length() - 1, j = end; char chs[] = s.toCharArray();
while(i < j) {
if (chs[i] == chs[j]) {
i++; j--;
} else {
i = 0; end--; j = end;
}
}
return new StringBuilder(s.substring(end+1)).reverse().toString() + s;
}
TODO: KMPhttps://discuss.leetcode.com/topic/27261/clean-kmp-solution-with-super-detailed-explanation
LeetCode [267] Palindrome Permutation II
Given a string s, return all the palindromic permutations (without duplicates) of it. Return an empty list if no palindromic permutation could be form.
https://discuss.leetcode.com/topic/30850/java-6ms-solution-no-reversal-or-concat
https://discuss.leetcode.com/topic/22214/ac-java-solution-with-explanation
Next Element
Given a number, find the next smallest palindrome larger than this number.
- if leftsmaller, then num[mid] += 1; and continue to add carry to previous element unitl it's 0
Check for Palindrome after every character replacement Query
- Save state and update state during each query
Anagram is A Palindrome
- freqMap
Check if binary representation of a number is palindrome
if (isKthBitSet(x, l) != isKthBitSet(x, r)) return false
- Save state and update state during each query
Anagram is A Palindrome
- freqMap
Check if binary representation of a number is palindrome
if (isKthBitSet(x, l) != isKthBitSet(x, r)) return false