Palindrome coding pattern

23 min readJul 8, 2024

A phrase is a palindrome if it reads the same forward and backward. In this post we will go through various coding pattern related to Palindrome related problems.

We can simply match original word with its reverse to check for palindrome.

Q. How to find out a string is a palindrome or not?

Approach#1

Use two pointers and compare each character.

bool isPalindrome (string s) {
  int n = s.size();
  int left=0, right=n-1;
  while(left < right) {
    if(s[left] !== s[right]) {
      return false;
    }
  }
  return true;
}

Approach#2

Reverse string and match it with original one.

bool isPalindrome (string s) {
  string rev = s; // c++ create a copy on value assignation
  sort(rev.begin(), rev.end()); // reverse the string
  return s == rev;
}

String substring vs partition

Many string problems are based on substring or partitions. These two sounds similar but both are entirly different.

For the string “hello”, the substrings are:

"h", "he", "hel", "hell", "hello"
"e", "el", "ell", "ello"
"l", "ll", "llo"
"l", "lo"
"o"

The partitions are:

["h", "e", "l", "l", "o"]
["h", "e", "l", "lo"]
["h", "e", "ll", "o"]
["h", "e", "llo"]
["h", "el", "l", "o"]
["h", "el", "lo"]
["h", "ell", "o"]
["h", "ello"]
["he", "l", "l", "o"]
["he", "l", "lo"]
["he", "ll", "o"]
["he", "llo"]
["hel", "l", "o"]
["hel", "lo"]
["hell", "o"]
["hello"]

Let’s see how we can write code for these two.

Code to generate substring.

public class SubstringPrinter {
    public static void main(String[] args) {
        String s = "hello";
        List<String> substrings = printSubstrings(s);
        System.out.println(substrings);
    }

    public static List<String> printSubstrings(String s) {
        List<String> substrings = new ArrayList<>();
        int n = s.length();

        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                substrings.add(s.substring(i, j+1));
            }
        }
        return substrings;
    }
}

Code to generate partitions

public static List<List<String>> printPartitions(String s) {
        List<List<String>> ans = new ArrayList<>();
        partitionHelper(s, 0, new ArrayList<>(), ans);
        return ans;
    }

private static void partitionHelper(String s, int i, List<String> partition, List<List<String>> ans) {
    int n = s.length();
    if (i == n) {
        ans.add(new ArrayList<>(partition));
        return;
    }

    for (int j= i; j< n; j++) {
        String prefix = s.substring(i, j+ 1);
        partition.add(prefix);
        partitionHelper(s, j+ 1, partition, ans);
        partition.remove(partition.size() - 1); // backtrack
    }
}

Let’s solve few problem related to palindrome to understand the concepts in better way.

125. Valid Palindrome

https://leetcode.com/problems/valid-palindrome/description/

Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome.

Approach: Two pointers

We can use left and right two pointers and scan each char to verify the palindrome.

class Solution {
public:
    bool isPalindrome(string s) {
        int n = s.size();
        int left = 0, right = n - 1;
        while (left < right) {
            if (!isalnum(s[left])) {
                left++;
                continue;
            }
            if (!isalnum(s[right])) {
                right--;
                continue;
            }
            if (tolower(s[left]) != tolower(s[right])) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
};

680. Valid Palindrome II

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

Given a string s, return true if the s can be palindrome after deleting at most one character from it.

Input: s = "abca"
Output: true
Explanation: You could delete the character 'c'.

Approach #1 Use recursion to control deleted char (OOM)

We can keep track of deleted char and do not allow deleting more if already deleted one.

class Solution {
private:
    bool recursion(string s, int i, int j, int k) {
        if (i >= j) {
            return true;
        }
        if (s[i] == s[j]) {
            return recursion(s, i + 1, j - 1, k);
        }
        if (k == 0) {
            return false;
        }
        // Delete one char either form left or right
        return recursion(s, i, j - 1, k - 1) || recursion(s, i + 1, j, k - 1);
    }

public:
    bool validPalindrome(string s) {
        int n = s.size();
        return recursion(s, 0, n - 1, 1);
    }
};

Approach #2 Use recursion to control deleted char with memory optimization

Instead of everytime we launch recursion, we can launch only on mismatch. This helps to reduce the stack memory used by recursion call stack.

class Solution {
private:
    bool recursion(string s, int i, int j, int k) {
        while (i < j) {
            // Launch recursion only on mismatch
            if (s[i] != s[j]) {
                if (k == 0) {
                    return false;
                }
                // Delete one char either form left or right
                return recursion(s, i, j - 1, k - 1) ||
                       recursion(s, i + 1, j, k - 1);
            }
            i++;
            j--;
        }
        return true;
    }

public:
    bool validPalindrome(string s) {
        int n = s.size();
        return recursion(s, 0, n - 1, 1);
    }
};

1216. Valid Palindrome III

https://leetcode.com/problems/valid-palindrome-iii/description/

Given a string s and an integer k, return true if s is a k-palindrome.

A string is k-palindrome if it can be transformed into a palindrome by removing at most k characters from it.

Input: s = "abcdeca", k = 2
Output: true
Explanation: Remove 'b' and 'e' characters.

Approach #1: Optimize recursion with condition on k (TLE)

We can apply similar recursion approach with k , but this will lead to TLE. Following is code for reference.

const isPalindrome = (s, i, j, k) => {
    while (i < j) {
        if (s[i] !== s[j]) {
            // If can't delete anymore
            if (k === 0) {
                return false;
            }
            // Either delete ith or jth
            return isPalindrome(s, i + 1, j, k - 1) ||
                isPalindrome(s, i, j - 1, k - 1);
        }
        i++;
        j--;
    }
    return true;
}
/**
 * @param {string} s
 * @param {number} k
 * @return {boolean}
 */
var isValidPalindrome = function (s, k) {
    return isPalindrome(s, 0, s.length - 1, k);
};

Approach #2: Apply recursion with memoization

We can apply memoization to avoid repeat solving same problem again and again.

const isPalindrome = (s, i, j, k, dp) => {
    const key = `${i}-${j}-${k}`;
    if (dp.has(key)) {
        return dp.get(key);
    }
    while (i < j) {
        if (s[i] !== s[j]) {
            // If can't delete anymore
            if (k === 0) {
                dp.set(key, false);
                return false;
            }
            // Either delete ith or jth
            const result = isPalindrome(s, i + 1, j, k - 1, dp) ||
                isPalindrome(s, i, j - 1, k - 1, dp);
            dp.set(key, result);
            return result;
        }
        i++;
        j--;
    }
    dp.set(key, true);
    return true;
}
/**
 * @param {string} s
 * @param {number} k
 * @return {boolean}
 */
var isValidPalindrome = function (s, k) {
    const dp = new Map();
    return isPalindrome(s, 0, s.length- 1, k, dp);
};

Approach#3: recursion code to count minimum chars needs to be deleted

Instead of feeding k to recursion method, we can update recursion code to return how many chars needs to be deleted to make string palindrome as below.

const isPalindrome = (s, i, j, dp) => {
    const key = `${i}-${j}`;
    if (dp.has(key)) {
        return dp.get(key);
    }
    let count = 0;
    while (i < j) {
        if (s[i] !== s[j]) {
            // Either delete ith or jth
            const result = 1 + Math.min(isPalindrome(s, i + 1, j, dp),
                isPalindrome(s, i, j - 1, dp));
            dp.set(key, result);
            return dp.get(key);
        }
        i++;
        j--;
    }
    dp.set(key, count);
    return dp.get(key);
}
/**
 * @param {string} s
 * @param {number} k
 * @return {boolean}
 */
var isValidPalindrome = function (s, k) {
    const dp = new Map();
    return isPalindrome(s, 0, s.length - 1, dp) <= k;
};

Approach #4: bottom up dp to count minimum chars needs to be deleted

Above code can also be easily written to bottom up dynamic programming as below.

f(i,j) = min char to be removed to make i...j a palindrome (i <= j)
f(i,i) = 0
f(i,j) = f(i+1, j-1) //  s[i] === s[j]
f(i,j) = 1 + min(f(i+1, j), f(i, j-1))  s[i] !== s[j]
# Relation with size
j - i = size - 1
j = i + size - 1;

Following is the code to implement this.

/**
 * @param {string} s
 * @param {number} k
 * @return {boolean}
 */
var isValidPalindrome = function (s, k) {
    const n = s.length;
    const dp = new Array(n).fill(0).map(a => new Array(n).fill(0));
    // Fill table as per increasing size
    for (let size = 2; size < n + 1; size++) {
        for (let i = 0; i < n - size + 1; i++) {
            const j = i + size - 1;
            if (s[i] === s[j]) {
                dp[i][j] = dp[i + 1][j - 1];
            } else {
                dp[i][j] = 1 + Math.min(dp[i + 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[0][n - 1] <= k;
};

214. Shortest Palindrome

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

You are given a string s. You can convert s to a palindrome by adding characters in front of it.

Return the shortest palindrome you can find by performing this transformation.

Example 1:

Input: s = "aacecaaa"
Output: "aaacecaaa"

Approach #1: Bruteforce — check every substring

In this problem, we can leverge the reverse string technique to find out the palindrome.

We can find the largest segment from the beginning that is a palindrome, and we can then easily reverse the remaining segment and append to the beginning. Following are steps to implement it.

Create the reverse of the original string s, say rev.
We would like to become greedy here i.e. we will start with comparing entire string of s to begin with the possibility of palindrome.
Then compare every substring from beginning to n-ito try if it is a palindrome or not.
If palindrome found then pre-append the rest at the beginning.

class Solution {
public:
    string shortestPalindrome(string s) {
        int n = s.size();
        string rev = string(s.rbegin(), s.rend());
        for (int i = 0; i < n; i++) {
            // memcmp to avoid creating substrings which might lead to oom
            if (memcmp(s.c_str(), rev.c_str() + i, n - i) == 0) {
                return rev.substr(0, i) + s;
            }
        }
        return "";
    }
};

Time complexity: O(n*n)

Approach #2: Using robin-karp rolling hash

We can use rolling hash technique to compare the substirng with approach#1. One difference is, we start comparing with smaller size than grow to bigger substring.

Following is code for reference.

class Solution {
public:
    string shortestPalindrome(string s) {
        int base = 26;
        int PRIME = pow(10, 9) + 7;
        long long forwardHash = 0, reverseHash = 0, powerValue = 1;
        int endIndex = -1;
        int n = s.size();
        // Calculate rolling hashes and find the longest palindromic prefix
        for (int i = 0; i < n; i++) {
            int chrValue = s[i] - 'a';
            forwardHash = (forwardHash * base + chrValue) % PRIME;
            reverseHash = (reverseHash + chrValue * powerValue) % PRIME;
            powerValue = (powerValue * base) % PRIME; // for reverse hash
            // If forward and reverse hashes match, update the palindrome end
            // index
            if (forwardHash == reverseHash) {
                endIndex = i;
            }
        }
        string suffix = s.substr(endIndex + 1);
        string reversedSuffix = string(suffix.rbegin(), suffix.rend());
        return reversedSuffix + s;
    }
};

Time complexity: O(n)

5. Longest Palindromic Substring

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

Given a string s, return the longest palindromic substring in s.

Example 1:

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

Example 2:

Input: s = "cbbd"
Output: "bb"

Approach

f(i,j): if substring is palindrome or not
axxxxxxb: if a === b && f(i+1,j-1) then f(i,j) is also palindrome
          if a === b && size==2 then also f(i,j) is palindrome

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function (s) {
    const n = s.length;
    const dp = new Array(n).fill(0).map(a => new Array(n).fill(false));
    // Every single len is a palindrome
    for (let i = 0; i < n; i++) {
        dp[i][i] = true;
    }
    let index = 0;
    let len = 1;
    for (let size = 2; size <= n; size++) {
        for (let i = 0; i < n - size + 1; i++) {
            const j = i + size - 1;
            if (s[i] === s[j] && (size === 2 || dp[i + 1][j - 1])) {
                dp[i][j] = true;
                // Track global answer
                if (size > len) {
                    index = i;
                    len = size;
                }
            }
        }
    }
    return s.substring(index, index + len);
};

647. Palindromic Substrings

https://leetcode.com/problems/palindromic-substrings/description/

Given a string s, return the number of palindromic substrings in it.

A string is a palindrome when it reads the same backward as forward.

A substring is a contiguous sequence of characters within the string.

Example 1:

Input: s = "abc"
Output: 3
Explanation: Three palindromic strings: "a", "b", "c".

Example 2:

Input: s = "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".

Approach

We can apply same approach as discussed in previous problem.

f(i,j): if substring is palindrome or not
axxxxxxb: if a === b && f(i+1,j-1) then f(i,j) is also palindrome
          if a === b && size==2 then also f(i,j) is palindrome

/**
 * @param {string} s
 * @return {number}
 */
var countSubstrings = function(s) {
     const n = s.length;
     const dp = new Array(n).fill(0).map(a => new Array(n).fill(false));
     // single len
     let ans =0;
     for (let i=0; i < n; i++) {
        ans++;
        dp[i][i] = true;
     }
     for (let size = 2; size < n + 1; size++) {
        for (let i=0; i < n - size + 1; i++) {
            const j = i + size - 1;
            if(s[i] === s[j] && (size == 2 || dp[i+1][j-1])) {
                ans++;
                dp[i][j] = true
            }
        }
     }
     return ans;
};

516. Longest Palindromic Subsequence

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

Given a string s, find the longest palindromic subsequence's length in s.

Input: s = "bbbab"
Output: 4
Explanation: One possible longest palindromic subsequence is "bbbb".

Approach

We can write following recursion function to solve this problem.

f(i,j) = longest palindromic subsequence between i & j
f(i,j = 1 // if i === j
f(i,j) = 2 + f(i+1, j-1) // if s[i] === s[j]
f(i,j) = max(
            f(i+1, j), // Delete left char
            f(i, j-1) // Delete right char
          )

Following is bottom up code to implement this approach.


/**
 * @param {string} s
 * @return {number}
 */
var longestPalindromeSubseq = function (s) {  
    const n = s.length;
    const dp = new Array(n).fill().map(a => new Array(n).fill(0));

    // Base case: single len string
    for (let i = 0; i < n; i++) {
        dp[i][i] = 1;
    }

    // Now process two size, three size onwards
    for (let size = 2; size <= n; size++) {
        for (let i = 0; i < n - size + 1; i++) {
            const j = i + size - 1;
            if (s[i] === s[j]) {
                dp[i][j] = 2 + dp[i + 1][j - 1];
            } else {
                dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1])
            }
        }
    }

    return dp[0][n - 1];
};

1682. Longest Palindromic Subsequence II

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

A subsequence of a string s is considered a good palindromic subsequence if:

It is a subsequence of s.
It is a palindrome (has the same value if reversed).
It has an even length.
No two consecutive characters are equal, except the two middle ones.

For example, if s = "abcabcabb", then "abba" is considered a good palindromic subsequence, while "bcb" (not even length) and "bbbb" (has equal consecutive characters) are not.

Given a string s, return the length of the longest good palindromic subsequence in s.

Input: s = "bbabab"
Output: 4
Explanation: The longest good palindromic subsequence of s is "baab".

Approach

We can come up with following recursive relationship.

f(i, j): len of longest good palindromic subsequence
f(i,j): 0 if i==j // To support no odd length
f(i,j):  previous char would be (i-1, j + 1). 
f(i,j): We need to make sure not same as prev char.
f(i,j) = 2 + f(i+1, j-1)//if s[i] === s[j] and not same as prev char or size=2
f(i,j) = max(
            f(i+1, j), // Delete left char
            f(i, j-1) // Delete right char
          )

Following is the code to implement this.

/**
 * @param {string} s
 * @return {number}
 */
var longestPalindromeSubseq = function (s) {
    const n = s.length;
    const dp = new Array(n).fill().map(a => new Array(n).fill(0));
    for (let size =2; size < n +1; size++) {
        for (let i=0; i < n - size + 1; i++) {
            const j = i + size - 1;
            if(s[i] === s[j] && (size === 2 || s[i] !== s[i+1])) {
                dp[i][j] = 2 + dp[i+1][j-1];
            } else {
                dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
            }
        }
    }
    return dp[0][n - 1];
};

1312. Minimum Insertion Steps to Make a String Palindrome

https://leetcode.com/problems/minimum-insertion-steps-to-make-a-string-palindrome/description/

TBD

131. Palindrome Partitioning

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

Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s.

Input: s = "aab"
Output: [["a","a","b"],["aa","b"]]

Approach

Generate all possible substrings of a string by partitioning at every index until we reach the end of the string.
Each generated substring is considered as a potential candidate if it a palindrome.

Code to print all partitions

String abba can be partitions as below.

[
    [ 'a', 'b', 'b', 'a' ],
    [ 'a', 'b', 'ba' ],
    [ 'a', 'bb', 'a' ],
    [ 'a', 'bba' ],
    [ 'ab', 'b', 'a' ],
    [ 'ab', 'ba' ],
    [ 'abb', 'a' ],
    [ 'abba' ]
  ]

Following is recursive code to generate all possible partitions.

/**
 * @param {string} s
 * @return {string[][]}
 */
var partition = function(s) {
    const n = s.length;
    const ans = [];
    const recurisve = (s, path) => {
        if(!s) {
            ans.push([...path]);
            return;
        }
        // Try all possible partition
        for (let i=0; i < s.length; i++) {
            const cur = s.substring(0, i + 1);
            path.push(cur);
            recurisve(s.substring(i+1), path);
            path.pop(); // backtrack and remove the current partition
        }
    }
    recurisve(s, []);
    return ans;
};

Above code is mutating the input therefore we can’t apply any memoization therefore let’s rewrite above code as below.

/**
 * @param {string} s
 * @return {string[][]}
 */
var partition = function (s) {
    const n = s.length;
    const ans = [];
    const recurisve = (i, path) => {
        if (i === n) {
            ans.push([...path]);
            return;
        }
        // Try all possible partition
        for (let j = i; j < s.length; j++) {
            const cur = s.substring(i, j + 1);
            path.push(cur);
            recurisve(j + 1, path);
            path.pop(); // backtrack and remove the current partition
        }
    }
    recurisve(0, []);
    return ans;
};

Code to print all partitions with each partition as a valid palindrome

We can use dp[i][j] = true/false to store the decision for a substring if it is a palindrome or not. Then we can use it every time to reuse the decision.

/**
 * @param {string} s
 * @return {string[][]}
 */
var partition = function (s) {
    const n = s.length;
    const dp = new Array(n).fill(0).map(a => new Array(n).fill(false));
    const ans = [];
    const recurisve = (i, path) => {
        if (i === n) {
            ans.push([...path]);
            return;
        }
        // Try all possible partition
        for (let j = i; j < s.length; j++) {
            // if char is same and inner substring is also a palindrome
            if (s[i] === s[j] && (j - i <= 2 || dp[i + 1][j - 1])) {
                dp[i][j] = true;
                const cur = s.substring(i, j + 1);
                path.push(cur);
                recurisve(j + 1, path);
                path.pop(); // backtrack and remove the current partition
            }
        }
    }
    recurisve(0, []);
    return ans;
};

132. Palindrome Partitioning II

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

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.

Approach 1: Use above code and update answer section to keep track of minimum partition (TLE)

/**
 * @param {string} s
 * @return {number}
 */
var minCut = function (s) {
    const n = s.length;
    const dp = new Array(n).fill(0).map(a => new Array(n).fill(false));
    let ans = n - 1;
    const recurisve = (i, path) => {
        if (i === n) {
            ans = Math.min(ans, path.length - 1);
            return;
        }
        // Try all possible partition
        for (let j = i; j < s.length; j++) {
            // if char is same and inner substring is also a palindrome
            if (s[i] === s[j] && (j - i <= 2 || dp[i + 1][j - 1])) {
                dp[i][j] = true;
                const cur = s.substring(i, j + 1);
                path.push(cur);
                recurisve(j + 1, path);
                path.pop(); // backtrack and remove the current partition
            }
        }
    }
    recurisve(0, []);
    return ans;
};

Approach 2: Use two DP first to make palindrome decision and second to store the min cuts for f(i,j)

First we need to rewrite partitions generation code using f(i,j) pattern as below.

/**
 * @param {string} s
 * @return {number}
 */
var minCut = function (s) {
    const n = s.length;
    const dpPalindrome = new Array(n).fill(0).map(a => new Array(n).fill(-1));
    const dpMinCut = new Array(n).fill(0).map(a => new Array(n).fill(-1));
    const isPalindrome = (i, j) => {
        if (i >= j) {
            dpPalindrome[i][j] = true;
            return 1;
        }
        if (dpPalindrome[i][j] !== -1) {
            return dpPalindrome[i][j];
        }
        dpPalindrome[i][j] = s[i] === s[j] && isPalindrome(i + 1, j - 1);
        return dpPalindrome[i][j];
    }
    const recursion = (i, j) => {
        // Base case
        if (i === j || isPalindrome(i, j)) {
            dpMinCut[i][j] = 0;
            return 0;
        }
        if (dpMinCut[i][j] !== -1) {
            return dpMinCut[i][j];
        }
        // Try all possible partition
        let minimumCut = j - i;
        for (let pIndex = i; pIndex <= j; pIndex++) {
            // if palindrome then update min cuts
            if (isPalindrome(i, pIndex)) {
                const local = recursion(pIndex + 1, j);
                minimumCut = Math.min(minimumCut, 1 + local);
            }
        }
        dpMinCut[i][j] = minimumCut;
        return minimumCut;
    }
    return recursion(0, n - 1);
};

1278. Palindrome Partitioning III

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

You are given a string s containing lowercase letters and an integer k. You need to :

First, change some characters of s to other lowercase English letters.
Then divide s into k non-empty disjoint substrings such that each substring is a palindrome.

Return the minimal number of characters that you need to change to divide the string.

Approach# TBD

1745. Palindrome Partitioning IV

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

Given a string s, return true if it is possible to split the string s into three non-empty palindromic substrings. Otherwise, return false.

A string is said to be palindrome if it the same string when reversed.

Approach# TBD

266. Palindrome Permutation

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

Given a string s, return true if a permutation of the string could form a palindrome and false otherwise.

Approach

There should be only one odd size and remaining should be even.

/**
 * @param {string} s
 * @return {boolean}
 */
var canPermutePalindrome = function(s) {
    const map = {};
    for(let i=0; i < s.length; i++) {
        const chr = s[i];
        map[chr] = map[chr] ? map[chr] + 1 : 1;        
    }
    // there should be only one odd size and remaining should be even
    const counts = Object.values(map);
    let odd = 0;
    for(let i=0; i < counts.length; i++) {
        const count = counts[i];
        if(count % 2 !==0) {
           odd++; 
        }
    }
    return odd <= 1;
};

267. Palindrome Permutation II

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

Given a string s, return all the palindromic permutations (without duplicates) of it.

You may return the answer in any order. If s has no palindromic permutation, return an empty list.

Input: s = "aabb"
Output: ["abba","baab"]

Approach

We need following three steps to solve this problem.

First check if palindrome permutation is possible or not. If not then simply return empty list.
Use frequency map produced by step#1 to build the half of the palindrome string.
Simply run permutation algorithm to generate all the possible arrangement of half frequency string from step#2 and generate all the palindrome. Special consideration for odd char.

Following is the code to implement this approach.

const canPermutatePalindrome = (s, map) => {
    let odd  = 0;
    for (const chr of s) {
        map.set(chr, map.has(chr) ? map.get(chr) + 1: 1);
        if(map.get(chr) % 2 === 0) {
            odd--;
        } else {
            odd++;
        }
    }
    return odd <= 1;
}
const swap = (arr, i, j) => {
    [arr[i], arr[j]] = [arr[j], arr[i]];
}
const permutate = (arr, i, result, oddChr) => {
    // base case
    if(i === arr.length -1 || arr.length === 0) {
        result.push(arr.join('')+oddChr+[...arr].reverse().join(''));
        return;
    }
    const set = new Set();
    for (let j = i; j < arr.length; j++) {
        // skip already processed duplicate chr
        if(set.has(arr[j])) {
            continue;
        }
        set.add(arr[j]);
        swap(arr, i, j);
        permutate(arr, i+1, result, oddChr)
        swap(arr, i, j);  
    }
}
/**
 * @param {string} s
 * @return {string[]}
 */
var generatePalindromes = function(s) {
    /**
    
    */
    const map = new Map();
    const n = s.length;
    const st = new Array(Math.floor(n/2)).fill('');
    
    // if not possible to perumte then return early
    if(!canPermutatePalindrome(s, map)) {
        return [];
    }
    
    const halfFrequency = [];
    let oddChr = '';
    for (const [chr, count] of map) {
        if(count % 2 === 1) {
             oddChr = chr;  
        } 
        for (let j=0; j < Math.floor(count/2); j++) {
            halfFrequency.push(chr);                 
        }
    }
    const result = [];
    permutate(halfFrequency, 0, result, oddChr);
    
    return result;
};

Above code is based on inplace permutation generation. There is another approach based on frequencies. Following is code using different approach to generate the permutation.


/**
 * @param {string} s
 * @return {string[]}
 */
var generatePalindromes = function (s) {
    const map = new Map();
    const canPermutatePalindrome = () => {
        let odd = 0;
        for (const chr of s) {
            map.set(chr, map.has(chr) ? map.get(chr) + 1 : 1);
            if (map.get(chr) % 2 === 0) {
                odd--;
            } else {
                odd++;
            }
        }
        return odd <= 1;
    }
    // if not possible to perumte then return early
    if (!canPermutatePalindrome()) {
        return [];
    }

    const halfFrequency = new Map()
    let oddChr = '';
    for (const [chr, count] of map) {
        if (count % 2 === 1) {
            oddChr = chr;
            halfFrequency.set(chr, (count - 1) / 2);
        } else {
            halfFrequency.set(chr, count / 2);
        }
    }
    const n = s.length;
    let size = oddChr ? (n - 1) / 2 : n / 2;
    const ans = [];
    const permutate = (i, result) => {
        if (i === size) {
            const copy = [...result];
            ans.push(copy.join('') + oddChr + copy.reverse().join(''));
            return;
        }
        // apply all the choices at ith level
        for (const [key, val] of halfFrequency) {
            if (val === 0) {
                continue;
            }
            result.push(key);
            halfFrequency.set(key, val - 1);
            permutate(i + 1, result);
            result.pop();
            halfFrequency.set(key, val);
        }
    }
    permutate(0, []);
    return ans;
};

1400. Construct K Palindrome Strings

https://leetcode.com/problems/construct-k-palindrome-strings/description/

Given a string s and an integer k, return true if you can use all the characters in s to construct k palindrome strings or false otherwise.

Input: s = "annabelle", k = 2
Output: true
Explanation: You can construct two palindromes using all characters in s.
Some possible constructions "anna" + "elble", "anbna" + "elle", "anellena" + "b"

Approach

annabelle can be grouped into anna and elble as two palindromes. As well as into anbna and elle or anellena and b .
A palindrome can have odd length, and in that case we need at most one odd char.
Therefore to constructor k palindrome we need at most k odd characters.
Also, we can not create k Palindrome, if k > n

Based on these two observation, we can write code as below.

/**
 * @param {string} s
 * @param {number} k
 * @return {boolean}
 */
var canConstruct = function (s, k) {
    const n = s.length;
    // can not create k palindrom, if k > n
    if (k > n) {
        return false;
    }
    // get count of odd char
    const map = new Map();
    for (const chr of s) {
        map.set(chr, map.has(chr) ? map.get(chr) + 1 : 1);
    }
    let odd = 0;
    for (const [key, val] of map) {
        odd += val % 2;
    }
    return odd <= k;
};

336. Palindrome Pairs

https://leetcode.com/problems/palindrome-pairs/description/

You are given a 0-indexed array of unique strings words. A palindrome pair is a pair of integers (i, j) such that:

words[i] + words[j] (the concatenation of the two strings) is a palindrome

Return an array of all the palindrome pairs of words.

Input: words = ["abcd","dcba","lls","s","sssll"]
Output: [[0,1],[1,0],[3,2],[2,4]]
Explanation: The palindromes are ["abcddcba","dcbaabcd","slls","llssssll"]

Approach

For every pair of word1 and word2, we have following three cases to build the palindrome.

We can build Trie data structure to explore the pair of palindrome. We are looking for:

Words in the Trie that are the reverse of our current word.
Words in the Trie that start with the reverse of our current word and then finish in a palindrome.
Words in the Trie that are the reverse of the first part of our current word, and then what’s left of our current word forms a palindrome.

Because we are interested in the reverse of words, it makes sense to put all the words into the Trie in reverse.

For following words list we can build Trie as below with reverse of each word.

words = [ “A”, “B”, “BAN”, “BANANA”, “BAT”, “LOLCAT”, “MANA”, “NAB”, “NANA”, “NOON”, “ON”, “TA”, “TAC”]

Since question is asking to return the index therefore at each word node we will also store the index of word.

Now let’s use Trie to answer each use cases.

Case 1 with the Trie

Search for word in trie, if it found another word (as trie stores reverse) then we claim that we found the answer (make sure index is not same).

Case 2 with the Trie

On search word1, at the end if it is not end of a word then find the other words that only has a palindrome left.

Case 3 with the Trie

On search if we find a word and still have some letters left from our current word. If those letters that are left form a palindrome then we can say that pair of word makes palindrome.

Following is the code to implement this approach.

class Solution {
private:
    struct TrieNode {
        TrieNode* children[26] = {};
        vector<int> remaining;
        int wordId;
        TrieNode() : wordId(-1) {}
    };
    static bool isPalindrome(string& word, int i) {
        int n = word.size();
        int left = i, right = n - 1;
        while (left < right) {
            if (word[left] != word[right]) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
    struct Trie {
        TrieNode* root;
        Trie() { this->root = new TrieNode(); }
        void addWord(string word, int wordId) {
            int n = word.size();
            TrieNode* node = root;
            for (int i = 0; i < n; i++) {
                if (isPalindrome(word, i)) {
                    node->remaining.push_back(wordId);
                }
                char chr = word[i];
                int index = chr - 'a';
                if (node->children[index] == nullptr) {
                    node->children[index] = new TrieNode();
                }
                node = node->children[index];
            }
            node->wordId = wordId;
        }
        vector<int> search(string word, int wordId) {
            TrieNode* node = root;
            vector<int> ans;
            int n = word.size();
            for (int i = 0; i < n; i++) {
                // case #3: if remaining of search word is palindrome
                if (node->wordId != -1 && isPalindrome(word, i)) {
                    ans.push_back(node->wordId);
                }
                int index = word[i] - 'a';
                node = node->children[index];
                if (node == nullptr) {
                    break;
                }
            }
            if (node == nullptr) {
                return ans;
            }
            // case #1: exact match
            if (node->wordId != -1 && wordId != node->wordId) {
                ans.push_back(node->wordId);
            }
            // case#2: search word is exhausted, need to check if there are
            // palindromes in the subtree.
            for (int i : node->remaining) {
                ans.push_back(i);
            }
            return ans;
        }
    };

    Trie* buildTrie(vector<string>& words) {
        int n = words.size();
        Trie* trie = new Trie();
        for (int i = 0; i < n; i++) {
            string word = words[i];
            string reversed = string(word.rbegin(), word.rend());
            trie->addWord(reversed, i);
        }
        return trie;
    }

public:
    vector<vector<int>> palindromePairs(vector<string>& words) {
        int n = words.size();
        Trie* trie = buildTrie(words);
        vector<vector<int>> ans;
        for (int i = 0; i < n; i++) {
            string word = words[i];
            vector<int> match = trie->search(word, i);
            for (int j : match) {
                ans.push_back({i, j});
            }
        }
        return ans;
    }
};

Time complexity: O(N*K²), where N is the number of words and K is the average length of a word. This is because we iterate through each word and potentially its entire length in the Trie.

Space Complexity: O(N*K), where N is the number of words and K is the average length of a word. This is mainly due to the Trie structure, which stores the word indices.

9. Palindrome Number

https://leetcode.com/problems/palindrome-number/description/

Given an integer x, return true if x is a palindrome , and false otherwise.

Example 1:

Input: x = 121
Output: true
Explanation: 121 reads as 121 from left to right and from right to left.

Follow up: Could you solve it without converting the integer to a string?

Approach: Revert half of the number

Reverting the number itself, and then compare the number with original number, if they are the same, then the number is a palindrome.
However, if the reversed number is larger than int.MAX, we will hit integer overflow problem.
To avoid the overflow issue of the reverted number, we can only revert half of the int number.
The reverse of the last half of the palindrome should be the same as the first half of the number, if the number is a palindrome.
Now the question is, how do we know that we’ve reached the half of the number?
Since we divided the number by 10, and multiplied the reversed number by 10, when the original number is less than the reversed number, it means we’ve processed half of the number digits.

Following is code for reference.

/**
 * @param {number} x
 * @return {boolean}
 */
var isPalindrome = function (x) {
    // base case
    // when x < 0, x is not a palindrome.
    // Also if the last digit of the number is 0, in order to be a palindrome, the first digit of the number also needs to be 0. Only 0 satisfy this property.
    if (x < 0 || (x % 10 == 0 && x !== 0)) {
        return false;
    }
    let reverted = 0;
    while (x > reverted) {
        reverted = reverted * 10 + (x % 10);
        x = Math.floor(x / 10);
    }
    // When the length is an odd number, we can get rid of the middle digit by revertedNumber/10
    // since the middle digit doesn't matter in palidrome(it will always equal to itself), we can simply get rid of it.
    return x == reverted || x == Math.floor(reverted / 10);
};

This post is based on Leetcode problems on Palindrome.

Happy coding :-)

Palindrome coding pattern

String substring vs partition

125. Valid Palindrome

680. Valid Palindrome II

1216. Valid Palindrome III

214. Shortest Palindrome

5. Longest Palindromic Substring

647. Palindromic Substrings

516. Longest Palindromic Subsequence

1682. Longest Palindromic Subsequence II

1312. Minimum Insertion Steps to Make a String Palindrome

131. Palindrome Partitioning

132. Palindrome Partitioning II

1278. Palindrome Partitioning III

1745. Palindrome Partitioning IV

266. Palindrome Permutation

267. Palindrome Permutation II

1400. Construct K Palindrome Strings

336. Palindrome Pairs

9. Palindrome Number

Written by Dilip Kumar

No responses yet