Chapter 29 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


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”.

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.


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

29.4.2 Algo 2: DP


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的个数.

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

主要recurrence equation是:


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

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

29.5 All Palindrome Substrings


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

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 Idea 5: Rolling Hash

Average \(O(N)\)

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.

  • 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.


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

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;

// 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;

   // 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.


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字串集.

29.9.1 DFS

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

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

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


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){
    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;
            if(map.containsKey(chs[i])){ map.get(chs[i]).add(i); }
                List <Integer> tmp = new ArrayList <Integer> ();
        Set <Character> keySet = map.keySet();
        Iterator <Character> iter = keySet.iterator();
        List <String > results = new ArrayList <String> ();
            int size = map.get(ch).size();
            locations.put(ch, new Pointers(0,size-1));
        StringBuilder sb1 = new StringBuilder();
        StringBuilder sb2 = new StringBuilder();
        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();
            //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;
                int tmp1 = p.left;
                int tmp2 = p.right;
            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:





One possible longest palindromic subsequence is “bbbb”.

Example 2:





One possible longest palindromic subsequence is “bb”.

Desc: CLRS P405




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)

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


The DFS part is almost the same as problem subsets.

After some optimization:

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

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.


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.


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

29.18 Get Palindrome of a String with replacement

Find the minimum number of operation required to create palindromic string p from S.

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.

Solution 1: Brute Force


Solution 2: Manacher

Solution 3: KMP

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:

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.


Input: “abccccdd”
Output: 7

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

class Solution {
    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){
            if(i&1) has_odd=true;
        return r+(int)has_odd;