Palindromic Substring

Published: May 30, 2017

We often see problems related to a palindrome or palindromic something. Palindrome is, like “racecar,” a reversed and original are exactly the same string. We see really many types of palindrome related problems. Sometime, problems are based on palindromic substrings. Sometime, those are palindromic subsequences.

The most typical problem is asking the longest palindromic substring or subsequence. However, not just the longest, asking partitions is another popular problem. As for partition problems, palindromes should be substrings. This kind of problems can be solved by a dynamic programming. The dynamic programming solution creates a truthy table which will have trues when the index i to j is a palindrome.

I’m going to write down three types of palindromic substring related problems: the longest, minimum cuts, and printing all palindromic partitions.

Problem Description

Always, a string will be given to this sort of problems, for example, “aabcbd.” That’s it for an input. Then, problems ask what should be found: the longest, min cut (also partitions), print all palindromic partitions, etc. The longest is relatively easy problem since there’s only one the longest palindrome. Theoretically, multiple longests are possible. But, normally if one longest is found, that’s the answer. For example, “aabcbd” is given, the answer is “bcb.”

Min cut is more diffucult. It requires an optimal partitioning. Since a length one string is a palindrome, [a | a | b | c | b | d] (5 cuts) is one of the partitioning based on palindrome. However, it’s obvious 5-cut isn’t the optimal. [aa | bcd | d] (2 cuts) is the answer.

Printing all palindromic partitions is way more difficult. Some solutions don’t take a dynamic programming approach, like in the “Given a string, print all possible palindromic partitions.” When a dynamic approach is chosen, the solution will be two steps.

  1. create a table to find palindromes.
  2. recursively iterate the given string looking at the palindrome table.

The answer for “aabcbd” will be: [[a, a, b, c, b, d], [a, a, bcb, d], [aa, b, c, b, d], [aa, bcb, d]]

The idea to create a truthy table

The truthy table is a key to solve this kind of problems by a dynamic programming. The table saves true/false, whether index i to j is a palindrome or not. Values in the table are so-called, “states,” of the dynamic programming.

The table will be created expanding the range one by one, also shifting the starting index one by one. When filling out the table, a direction is diagonal, from upper left to lower right.


   a a b c b d
   _ _ _ _ _ _
a |\ \ \ \ \ \
a |  \ \ \ \ \
b |    \ \ \ \
c |      \ \ \
b |        \ \
d |          \

Going on by diagonal, i j indices will be incremented with an extra index k. The k expresses a length of substring.

for (int k = 3; k <= n; k++) {
    for (int i = 0; i < n - k + 1; i++) {
        int j = i + k - 1;
	    table[i][j] = ...
    }
}

The way to expand the length and check whether substring is a palindrome or not will be proceeded like this:


    a a b c b d       a a b c b d       a a b c b d       a a b c b d       a a b c b d       a a b c b d
    0 1 2 3 4 5       0 1 2 3 4 5       0 1 2 3 4 5       0 1 2 3 4 5       0 1 2 3 4 5       0 1 2 3 4 5
    _ _ _ _ _ _       _ _ _ _ _ _       _ _ _ _ _ _       _ _ _ _ _ _       _ _ _ _ _ _       - - - - - -
a 0|T             a 0|T T           a 0|T T F         a 0|T T F F       a 0|T T F F F     a 0|T T F F F F
a 1|  T           a 1|  T F         a 1|  T F F       a 1|  T F F F     a 1|  T F F F F   a 1|  T F F F F
b 2|    T         b 2|    T F       b 2|    T F T     b 2|    T F F F   b 2|    T F T F   b 2|    T F T F
c 3|      T       c 3|      T F     c 3|      T F F   c 3|      T F F   c 3|      T F F   c 3|      T F F
b 4|        T     b 4|        T F   b 4|        T F   b 4|        T F   b 4|        T F   b 4|        T F
ff5|          T   d 5|          T   d 5|          T   d 5|          T   d 5|          T   d 5|          T

The logic to check whether the substring from index i to j is a palindrome or not is:

  1. if characters at index i and j are the same,
  2. if a previous state (saved at index i + 1 and j - 1) is true,
  3. the position at index i and j will be true.

The idea to find the longest

The table saves whether the substring of index i to j is a palindrome or not. Given that, when the value is true, i - j + 1 is the length of palindrome. Checking all true positions and compare the length will give me the answer.

The idea to find minimum cuts

The same as the longest problem, minimum cuts sees the table. The cuts happens when the last character of the substring doesn’t form the palindrome. Otherwise, the boundary should be expanded one by one.

The idea to print all palindromic substrings

Likewise, looking at table, adds palindrome one by one, shifting the starting index. In this case, depth first search by recursion will be a good way to find palindromes from the rest of the substring.

Java code

Below is the Java code to find means anytime.

The result is:

longest: aa
min cuts: 1
all: [[a, a, b], [aa, b]]
longest: bcb
min cuts: 2
all: [[a, a, b, c, b, d], [a, a, bcb, d], [aa, b, c, b, d], [aa, bcb, d]]

Resources

Latest Posts

Vite + Vue + Bun on Rails

Vue.js is one of frontend frameworks gaining popularity among rapidly emerging JavaScript technologies. The combination of Vue.js and Rails is becoming more popular as well, however, Vue.js development on Rails is not so straightforward. The reason would be that Vue.js relies on Vite for a development environment such as HMR (Hot Module Replacement) and bundling.

Bun + React on Rails

In the frontend world, new technologies keep emerging rapidly these years. Still, React is a well-established and very popular frontend framework, Vue.js, Svelte, Astro and more frameworks are gaining popularity. Not just the frameworks, tools for a transpiler/bundler or sort are also under a rapid development. In JavaScript domain, esbuild, rollup, vite and some more are out.

Ruby on Rails Secrets Management

A web application needs various kinds of values, params and etc which should not be revealed to the public, say GitHub repo. For example, API keys, tokens, passwords, and endpoints, all those should be kept secret. Another important factor is that such secrets should be shared among the team members. Additionally, all those secrets should come along with the deployment.