Palindrome - Algorithm

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

- 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 palindromic subsequence
- 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/
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-explanation
public 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: KMP
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

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

Post a Comment

Labels

Java (159) Lucene-Solr (112) Interview (61) All (58) J2SE (53) Algorithm (45) Soft Skills (38) Eclipse (33) Code Example (31) Linux (25) JavaScript (23) Spring (22) Windows (22) Web Development (20) Tools (19) Nutch2 (18) Bugs (17) Debug (16) Defects (14) Text Mining (14) J2EE (13) Network (13) Troubleshooting (13) PowerShell (11) Chrome (9) Design (9) How to (9) Learning code (9) Performance (9) Problem Solving (9) UIMA (9) html (9) Http Client (8) Maven (8) Security (8) bat (8) blogger (8) Big Data (7) Continuous Integration (7) Google (7) Guava (7) JSON (7) Shell (7) ANT (6) Coding Skills (6) Database (6) Lesson Learned (6) Programmer Skills (6) Scala (6) Tips (6) css (6) Algorithm Series (5) Cache (5) Dynamic Languages (5) IDE (5) System Design (5) adsense (5) xml (5) AIX (4) Code Quality (4) GAE (4) Git (4) Good Programming Practices (4) Jackson (4) Memory Usage (4) Miscs (4) OpenNLP (4) Project Managment (4) Spark (4) Testing (4) ads (4) regular-expression (4) Android (3) Apache Spark (3) Become a Better You (3) Concurrency (3) Eclipse RCP (3) English (3) Happy Hacking (3) IBM (3) J2SE Knowledge Series (3) JAX-RS (3) Jetty (3) Restful Web Service (3) Script (3) regex (3) seo (3) .Net (2) Android Studio (2) Apache (2) Apache Procrun (2) Architecture (2) Batch (2) Bit Operation (2) Build (2) Building Scalable Web Sites (2) C# (2) C/C++ (2) CSV (2) Career (2) Cassandra (2) Distributed (2) Fiddler (2) Firefox (2) Google Drive (2) Gson (2) How to Interview (2) Html Parser (2) Http (2) Image Tools (2) JQuery (2) Jersey (2) LDAP (2) Life (2) Logging (2) Python (2) Software Issues (2) Storage (2) Text Search (2) xml parser (2) AOP (1) Application Design (1) AspectJ (1) Chrome DevTools (1) Cloud (1) Codility (1) Data Mining (1) Data Structure (1) ExceptionUtils (1) Exif (1) Feature Request (1) FindBugs (1) Greasemonkey (1) HTML5 (1) Httpd (1) I18N (1) IBM Java Thread Dump Analyzer (1) JDK Source Code (1) JDK8 (1) JMX (1) Lazy Developer (1) Mac (1) Machine Learning (1) Mobile (1) My Plan for 2010 (1) Netbeans (1) Notes (1) Operating System (1) Perl (1) Problems (1) Product Architecture (1) Programming Life (1) Quality (1) Redhat (1) Redis (1) Review (1) RxJava (1) Solutions logs (1) Team Management (1) Thread Dump Analyzer (1) Visualization (1) boilerpipe (1) htm (1) ongoing (1) procrun (1) rss (1)

Popular Posts