COUNTPAL - Editorial

editorial
, , ,
1

PROBLEM LINKS

Practice
Contest

DIFFICULTY

EASY

EXPLANATION

The problem can be solved easily by dynamic programming:

F(i) = CountPal(s’) for s’ is the subtring of s1…s[i]

so F(i) = sum of F(j) with j < i whether the substring of s[j+1]…s[i] is a palindrome.

To verify a substring is a palindrome or not, we can pre-compute to save time of DP.

Complexity: O(|s|^2)

1 Like
2

pls elaborate more clearly.

1 Like
3

please explain clearly…

4

Here is my detail explanation of solution.

Notation: we’ve got string s, and s[i] is character on i-th position. First character is on position 0, second on position 1 and so on. Total length of string is n, so last letter is s[n-1].

So first thing is dynamic programming itself. Denote F(i) number of different ways you can create substring s[0]s[1]…s[i-1] from only palindromes. Obviously the F(n) is result for our problem, because it’s number of ways for substring s[0]…s[n-1] so whole string s.

Now on the end of our substring s[0]…s[i] must be palindrome and we can tear off this palindrome. We try each position j and if substring s[j]…s[i-1] creates palindrome, than we can rip off this segment and we end up with substring s[0]…s[j-1]. This substring has F(j) ways to disintegrate, so we add to total number of ways in F(i) value F(j).

In other words, F(j) can be computed as sum of all F(j) when substring s[j]…s[i-1] creates palindrome.

int F(int i) {
    if(i==0) return 1;
    int res=0;
    for(int j=0; j<i; j++)
        if(substring s[j]...s[i-1] is palindrome) res+=F(j);
    return res;
}

Here is simple pseudocode to this function. Of course, if you want it fast enough, you must use memoization and each F(i) compute at most once. But without is clearer.

Last thing is, how we find out if some substring s[j]…s[i-1] is palindrome. This we can simply precompute or can be computed by the time. The smallest palindromes are with zero characters and one character, so for s[i]s[i-1] (notice that there is no character in this substring, because i>i-1) and s[i-1] is answer yes. Larger substring can be compute easily. If we get substring s[j]…s[i-1] than s[j] must be equal as s[i-1] and substring s[j+1]…s[i-2] must be palindrome.

Again simple pseudocode:

bool isPalindrome(int j, int i) {
    if(j==i || j+1==i) return true; //if substring is empty or contain one character
    if(s[j]!=s[i-1]) return false; //if first and last letters are different return false
    return isPalindrome(j+1, i-1);//first and last letters are equal, so return true if                                               s[j+1]...s[i-2] is palindrome
}

Don’t forget to use memoization in both function. Than you obtain time complexity O(n^2). And also use modulo :slight_smile:

To complete this solution, here is my whole correct implementation in C++

3 Likes