Chapter 29 Palindrome

这个专题讨论所有和palindrome相关的问题.

  • pal is an abbreviation of Palindrome in this section.

LPS - Longest Palindromic Subsequence
LPs - Longest Palindromic Substring
LCS - Longest Common Subsequence
LCs - Longest Common substring

问题可以是求长度,个数,或者求所有满足条件的结果.

https://leetcode.com/problemset/all/?search=palindrom

29.4 Number of All Palindrome Substrings

Given a string, your task is to count how many palindromic substrings in this string.

The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters.

Example 1:
Input: “abc”
Output: 3
Explanation: Three palindromic strings: “a”, “b”, “c”.

Example 2:
Input: “aaa”
Output: 6
Explanation: Six palindromic strings: “a”, “a”, “a”, “aa”, “aa”, “aaa”.

https://leetcode.com/problems/palindromic-substrings
http://www.geeksforgeeks.org/count-palindrome-sub-strings-string/

29.4.1 Algo 1: Expansion from current point

Naive的解法是找出所有的substring palindrome,一边找一边计数.T复杂度是: \(O(N^2)\).

In GFG, it requires length of palindrome substring is greater then or equal to 2.

这个空间复杂度为O(1).不过麻烦的是需要处理奇数和偶数的情况,所以我觉得速度应该没有下面的DP方法快.面试的时候能写出上面的解法就可以了.

In Leetcode, a single char could be a palindrome. So we need to add string size at the last line.

https://repl.it/FJUn

29.4.2 Algo 2: DP

需要一個isPalindrome的boolean上三角矩陣,如果是true就加1.

s[i] == s[j] and (i+1 == j || isp[i+1][j-1]) should be enough.

  • JAVA
  • Follow up: 如果要求任意substring包含多少palindrome, 用下面的方法. 用两个矩阵pals和counts. 一个矩阵pals表示是不是palindrome substring. 另一个矩阵counts表示包含的palindrome substring的个数.

pals[i][j]表示substringA.substr(i,j-i+1)是否是palindrome.
counts[i][j]表示substringA.substr(i,j-i+1)包含多少个palindrome sub-substring.

主要recurrence equation是:

counts[i][j]=counts[i][j-1]+counts[i+1][j]-counts[i+1][j-1]+(int)pals[i][j];

方法和DP解LPs类似. T复杂度也是\(O(N^2)\). 下面是C++代码:

注意leetcode上面的把单个字符也算成Palindrome.所以结果是: counts[0][L-1]+s.size();

29.5 All Palindrome Substrings

http://www.geeksforgeeks.org/find-number-distinct-palindromic-sub-strings-given-string/

这个可以用expansion的方法一个个找出来.

29.6 Longest Palindrome Substring (2D DP, Expansion, Manacher)

https://leetcode.com/problems/longest-palindromic-substring/

http://fisherlei.blogspot.com/2012/12/leetcode-longest-palindromic-substring.html

http://blog.csdn.net/feliciafay/article/details/16984031

29.6.2 Idea 2: 2D DP

  • Recurrence Equation

To tell if arbitrary substring \(A[i:j]\) is a palindrome.

\[ f(i,j)= \begin{cases} true, & \text{if } (f(i+1,j-1)=true) \text{ and } (A[i]=A[j]) \text{ and } (j > i+1 )\\ true, & \text{if } (A[i]=A[j]) \text{ and } (j = i+1 )\\ false, & \text{otherwise } \end{cases} \] where \(i,j\) are index, \(j-i+1\) is the length of pal.

  • Boundary Condition

\[f(i,i) = 1\] where \(0\leq i \leq L-1\)

Here we just only used half of the matrix.

Interestingly the boundary condition is the diagonal cells of the matrix from \(M[0][0]\) to \(M[L-1][L-1]\).

  • Coding
  1. how to loop in a half matrix
  2. fill the half matrix correctly

29.6.2.3 Idea 5: Rolling Hash

Average \(O(N)\)

http://aleclownes.com/2016/10/03/palindromic-rolling-hash.html

29.7 730. Count Different Palindromic Subsequences

Given a string S, find the number of different non-empty palindromic subsequences in S, and return that number modulo 10^9 + 7.

A subsequence of a string S is obtained by deleting 0 or more characters from S.

A sequence is palindromic if it is equal to the sequence reversed.

Two sequences A_1, A_2, … and B_1, B_2, … are different if there is some i for which A_i != B_i.

Example 1:
Input: S = ‘bccb’
Output: 6
Explanation: The 6 different non-empty palindromic subsequences are ‘b’, ‘c’, ‘bb’, ‘cc’, ‘bcb’, ‘bccb’.
Note that ‘bcb’ is counted only once, even though it occurs twice.

Example 2:
Input: S = ‘abcdabcdabcdabcdabcdabcdabcdabcddcbadcbadcbadcbadcbadcbadcbadcba’
Output: 104860361
Explanation: There are 3104860382 different non-empty palindromic subsequences, which is 104860361 modulo 10^9 + 7.

https://leetcode.com/problems/count-different-palindromic-subsequences/description/

  • CPP

Let dp[len][i][x] be the number of distinct palindromes of the subtring starting at i of length len, where the first (and last) character is x. The DP formula is simple :

If s[i] != x, then dp[len][i][x] = dp[len-1][i+1][x] (ignoring the first character in this window)
If s[i+len-1] != x then dp[len][i][x] = dp[len-1][i][x] (ignoring the last character in this window)
If both the first and last characters are x, then we need to count the number of distinct palindromes in the sub-window from i+1 to i + len -2. Need to be careful with how we count empty string.
Since we only need to subproblems of length len-1, len-2, we only need to remember the solutions for the subproblems of length len, len-1, len-2. This is needed to pass the max test case.
  • Java

29.8 Number of All Palindromic subsequence

Find how many palindromic subsequence (need not necessarily be distinct) can be formed in a given string. Note that the empty string is not considered as a palindrome.

Examples:

Input : str = "abcd"
Output : 4
Explanation :- palindromic  subsequence are : "a" ,"b", "c" ,"d" 

Input : str = "aab"
Output : 4
Explanation :- palindromic subsequence are :"a", "a", "b", "aa"

Input : str = "aaaa"
Output : 15

http://www.geeksforgeeks.org/count-palindromic-subsequence-given-string/

Find how many palindromic subsequence (need not necessarily be distinct) can be formed in a given string. Note that the empty string is not considered as a palindrome.

The above problem can be recursively defined.

Initial Values : i= 0, j= n-1;

CountPS(i,j)
// Every single character of a string is a palindrome 
// subsequence 
if i == j
   return 1 // palindrome of length 1

// If first and last characters are same, then we 
// consider it as palindrome subsequence and check
// for the rest subsequence (i+1, j), (i, j-1)
Else if (str[i] == str[j)]
   return   countPS(i+1, j) + countPS(i, j-1) + 1;

else
   // check for rest sub-sequence and  remove common
   // palindromic subsequences as they are counted
   // twice when we do countPS(i+1, j) + countPS(i,j-1)
   return countPS(i+1, j) + countPS(i, j-1) - countPS(i+1, j-1) 

If we draw recursion tree of above recursive solution, we can observe overlapping Subprolems. Since the problem has overlapping subproblems, we can solve it efficiently using Dynamic Programming.

OJ: https://www.codechef.com/problems/CB03

This is very similar to number of all Palindrome Substring except line 11. 这是有原因的.举例说明’aba’

ab-> s[0], s[1] -> r1=2
ba-> s[1], s[2] -> r2=2
b-> s[1] -> r3=1
s[0]==s[2] -> r4 = 1(s[0],s[2]) + 1*r1 (s[0],s[1],s[2])

total: N = r1+r2+r4-r3 = r1+r2+1 (这里r4-r3永远等于1.)

还有这里结果中允许重复字符串.

29.9 All Palindrome Subsequences

另一种表述是一个字符串删除任意字符形成的所有Palindrome: 给一个string, 可以删除任意字符,求所有可以得到的palidrome字串集.

http://www.mitbbs.com/article/JobHunting/33053715_3.html

29.9.1 DFS

网上看到的号称完美解法:无重复的逐一完全遍历所有的substring palindrome.复杂度就是O(the number of palindrome subsequences).

http://www.mitbbs.com/article_t/JobHunting/33053715.html

因为我不懂java和javascript, 所以先记录在这里.

发信人: Ilikemac (一低头的温柔), 信区: JobHunting
标  题: Re: LinkedIn onsite一道题
发信站: BBS 未名空间站 (Mon Nov  9 15:12:19 2015, 美东)

我的java实现,参考了Blaze的思路,不过不知道真正理解了他的思路没有,因为我不
太看得懂javascript.下面是几个点:

1. 这个题目用的是backtracking而不是dp,因为dp不可能给你产生排列组合.dp通常
就是给你一个最值.
2. 时间复杂度是指数级.
3. 题目的本质是产生排列.
4. 一般的backtracking来形成字符串的话,从现有字母集中每次任意挑一个字母,然后
从剩下的字母里继续挑.把所有字母都加到字符串里面去了,这轮程序也就完了.这个
题目因为有个顺序的限制条件,决定程序怎样进行下去并不能用剩下多少字符来决定,
而应该是用已经加入字符串的字母的位置来决定.
import java.util.HashMap;
import java.util.List;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.Set;
public class Example5 {
    public static void main(String [] args){
        Example5 o = new Example5();
        List <String> results = o.setUp("abcbabcba");
        for(String str: results){
            System.out.println(str);
        }
    }
    public List <String> setUp(String palidrome){
        HashMap <Character, List<Integer>> map = new HashMap <Character, List<Integer>>();
        HashMap <Character, Pointers> locations = new HashMap <Character, Pointers>();
        char [] chs = palidrome.toCharArray();
        int i = 0;
        for(i=0;i<chs.length;i++){
            if(map.containsKey(chs[i])){ map.get(chs[i]).add(i); }
            else{
                List <Integer> tmp = new ArrayList <Integer> ();
                tmp.add(i);
                map.put(chs[i],tmp);
            }
        }
        Set <Character> keySet = map.keySet();
        Iterator <Character> iter = keySet.iterator();
        List <String > results = new ArrayList <String> ();
        while(iter.hasNext()){
            Character ch=iter.next();
            //results.add(ch.toString());
            int size = map.get(ch).size();
            locations.put(ch, new Pointers(0,size-1));
        }
        StringBuilder sb1 = new StringBuilder();
        StringBuilder sb2 = new StringBuilder();
        dfs(results,0,chs.length-1,sb1,sb2,keySet,map,locations);
        return results;                    
    }
    private class Pointers {
        int left;
        int right;
        public Pointers(int left, int right){
            this.left = left;
            this.right = right;
        }
    }
    public void dfs (List <String> results, int left, int right,
      StringBuilder sb1, StringBuilder sb2, Set <Character> keySet, 
      HashMap < Character, List<Integer>> map, HashMap <Character, Pointers> locations)
    {
        Iterator <Character> iter = keySet.iterator();
        while(iter.hasNext()){
            Character ch=iter.next();
            //System.out.println("ch="+ch+" left="+left+" right="+right);
            Pointers p=locations.get(ch);
            //System.out.println("left1="+p.left+" right1="+p.right);
            List <Integer> nums = map.get(ch);
            int oldLeft = p.left;
            int oldRight = p.right;
            while((p.left<=p.right)&&(nums.get(p.left)<left)){
                p.left++;
            }
            while((p.left<=p.right)&&(nums.get(p.right)>right)){
                p.right--;
            }
            if(p.left<=p.right){
                results.add(sb1.toString()+ch+sb2.toString());
                //System.out.println(sb1.toString()+ch+sb2.toString());
            }
            if(p.left<p.right){
                sb1.append(ch);
                sb2.insert(0,ch);
                int tmp1 = p.left;
                int tmp2 = p.right;
                p.left++;
                p.right--;
                //System.out.println(sb1.toString()+sb2.toString());
                results.add(sb1.toString()+sb2.toString());
                dfs(results,nums.get(tmp1)+1,nums.get(tmp2)-1,sb1,sb2,keySet,map,locations);
                sb1.deleteCharAt(sb1.length()-1);
                sb2.deleteCharAt(0);
            }
            p.left = oldLeft;
            p.right = oldRight;
        }
    }
}

29.10 516. Longest Palindromic Subsequence

Given a string s, find the longest palindromic subsequence’s length in s. You may assume that the maximum length of s is 1000.

Example 1:

Input:

"bbbab"

Output:

4

One possible longest palindromic subsequence is “bbbb”.

Example 2:

Input:

"cbbd"

Output:

2

One possible longest palindromic subsequence is “bb”.

https://leetcode.com/problems/longest-palindromic-subsequence

Desc: CLRS P405

pals[i][j]表示substringA.substr(i,j-i+1)所包含的LPS的长度..

Algorithm:

这个算法先求出LPS的长度.但是不是subsequence本身.要求出本身需要回溯.

http://www.geeksforgeeks.org/dynamic-programming-set-12-longest-palindromic-subsequence/

Top Down:

Bottom Up:

  • JAVA
  • Super simple solution using reversed string

If you know how to find LCS between 2 strings, then this problems can be reduced to finding the LCS between the original string and its reversed form:

Just find length:

29.13 Palindrome Partitioning (2d DP + subsets DFS)

https://leetcode.com/problems/palindrome-partitioning/

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

For example, given s = “aab”, Return

[
  ["aa","b"],
  ["a","a","b"]
]

The DFS part is almost the same as problem subsets.

After some optimization:

29.14 132. Palindrome Partitioning II(2d DP+ 1d DP)

https://leetcode.com/problems/palindrome-partitioning-ii/

Given a string s, partition s such that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

For example, given s = “aab”, return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.

cut[i]表示子串s[0…i]所需要的最小分割数

29.16 266. Palindrome Permutation

Given a string, determine if a permutation of the string could form a palindrome. For example, “code” -> False, “aab” -> True, “carerac” -> True.

这题结合了Palindrome和Permutation两个重要概念.

https://leetcode.com/problems/palindrome-permutation/

因为ASCII码包括扩展的范围是[0,255].所以用类似counting sort的方法.这里不是计数递增,而是不断flip,因为只需判断奇偶性.

http://en.cppreference.com/w/cpp/utility/bitset

29.18 Get Palindrome of a String with replacement

Find the minimum number of operation required to create palindromic string p from S.
https://discuss.codechef.com/questions/86490/linkedin-placement-test-question-get-palindrome-of-a-string-with-replacement

Elina has a string S, consisting of lowercase English alphabetic letters(ie. a-z). She can replace any character in the string with any other character, and she can perform this replacement any number of times. she wants to create a palindromic string p from s such that string p contains the sub string linkedin. it is guaranteed that Elina can create palindromic string p from S. find the minimum number of operation required to create palindromic string p from S. Sample test case are:

First test case: S=“linkedininininin” explanation :

linkedin (i) (n) (i) (n) (i) ni (n)
         (n) (i) (d) (e) (k)    (l)  
p =  "linkedinnideknil" 

output is 6

Second test case: S=“fulrokxeuolnzxltiiniabudyyozvulqbydmaldbxaddmkobhlplkaplgndnksqidkaenxdacqtsskdkdddls”

output is 46

29.20 214. 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.

For example:

Given "aacecaaa", return "aaacecaaa".
Given "abcd", return "dcbabcd".

This problem is indeed computing the longest palindromic prefix of a string s.

https://leetcode.com/problems/shortest-palindrome/

Solution 1: Brute Force

\(O(N)\)的解决方法是基于马拉车KMP.

Solution 2: Manacher

https://discuss.leetcode.com/topic/21739/easy-c-manacher

Solution 3: KMP

http://bookshadow.com/weblog/2015/05/22/leetcode-shortest-palindrome/

Solution 4: Rolling Hash \(O(MN)\)

How to construct hash? Here we construct two hashes with reverse order.

strinng    hash1    hash2
A          1        1
AB         12       21
ABC        123      321
ABCB       1232     2321
ABCBA      12321    12321

When we find a palindrome, the two hashes are equal!
自己先写了一次,包含spurious hit检测的.

注意substr(size_type pos = 0, size_type count = npos)是returns a substring [pos, pos+count),包含pos那一点.

如果不包含spurious hit check, the speed is 3ms! Your runtime beats 94.28% of cpp submissions!!

See discussion: https://discuss.leetcode.com/topic/41599/8-line-o-n-method-using-rabin-karp-rolling-hash
Others:
https://discuss.leetcode.com/topic/47699/accepted-c-solution-easy-to-understand

29.22 409. Longest Palindrome

Given a string which consists of lowercase or uppercase letters, find the length of the longest palindromes that can be built with those letters.

This is case sensitive, for example “Aa” is not considered a palindrome here.

Note: Assume the length of given string will not exceed 1,010.

Example:

Input: “abccccdd”
Output: 7

Explanation: One longest palindrome that can be built is “dccaccd”, whose length is 7.

https://leetcode.com/problems/longest-palindrome/

class Solution {
public:
    int longestPalindrome(string s) {
        vector<int> m(256);
        for(char c: s) m[c]++;
        int r=0;
        bool has_odd=false;
        for(int i: m){
            r+=i/2*2;
            if(i&1) has_odd=true;
        }
        return r+(int)has_odd;
    }
};