Number of Palindromic paths in a Matrix | Part 20

Hello guys, welcome back to “code with asharam”. This is 20th part of my dynamic programming tutorials. I will discuss a really interesting problem this time – Number of Palindromic paths in a Matrix. If at any moment it feels like that things are going over your head, then, I advice to go through all the last tutorials. Even after that if you are stuck somewhere, then, feel free to leave a comment or send me a mail. I will answer your query as soon as possible. So, without any further delay, let’s take a dive into deep oceans of dynamic programming.

Number of Palindromic paths in a Matrix

Given a matrix S of size N*M containing lower alphabetical characters only, we need to count number of palindromic paths in the matrix. A path is defined as a sequence of cells starting from top left cell and ending at bottom-right cell. We are allowed to move to right and down only from current cell.
source of problem statement :- geeksforgeeks

Give it a try on your own before moving forward

Approaching the problem

As I always tell you that our way of solving method using dynamic programming is an universal. We will play our game of guessing what is happening, what can or what cannot happen. Before moving forward, let’s make few observations which we can make just by looking at the problem:

  1. Since our path is palindromic, S[1][1] should be equal to S[N][M].
  2. After starting from (1, 1), we can either move to (1, 2) or (2, 1). Suppose we move to (1, 2). Now, we can reach (N, M) from either (N-1, M) or (N, M-1). Let’s say we reach from (N-1, M). On careful observation you can see that we have to move from (1, 2) to (N-1, M) along a palindromic path. In other words, we have to travel a submatrix whose upper left corner is (1, 2) and bottom right corner is (N-1, M). So, we have divided problem from ((1, 1), (N, M)) to ((1, 2), (N-1, M)).
  3. We just considered one subproblem in the last point. But there will be 4 subproblems: ((1, 2), (N-1, M)), ((2, 1), (N-1, M)), ((1, 2), (N, M-1)), ((2, 1), (N, M-1)).

We can extend these observations for a general beginning point (bi, bj) to ending point (ci, cj) as follows:

path(bi, bj, ci, cj) denotes number of palindromic path from (bi, bj) to (ci, cj)

path(bi, bj, ci, cj) = path(bi+1, bj, ci-1, cj) +
                       path(bi+1, bj, ci, cj-1) +
                       path(bi, bj+1, ci-1, cj) +
                       path(bi, bj+1, ci, cj-1)
Memoization and code

As you can see that we have generated an algorithm pretty fast. But still we have to provide base case and do something about problem of overlapping of subproblems. As you can see that if bi > ci or ci > cj, then, we cannot reach our destination due to the restriction that we cannot move up or left. Hence, path() will return 0 in this case. Also if S[bi][bj] != S[ci][cj], then, according to point #1, path() will return 0. If the last 2 conditions are not satisfied and beginning and ending coordinate are adjacent, then, clearly there is only 1 path possible and hence, path() will return 1.
We have discussed the base cases and now, let’s do something about the overlapping of subproblems. path() takes four argument out of which bi and ci can take values from 1 to N and bj and cj can take values from 1 to M. Hence, path() can take N2*M2 distinct arguments and we need a 4-d array of size N*M*N*M. Let’s see how our modified algorithm looks like:

path(bi, bj, ci, cj) = 0 if bi > ci or ci > cj or S[bi][bj] != S[ci][cj]
                       1 if abs(bi-ci) + abs(bj-cj) = 1
                       dp[bi][bj][ci][cj] if already computed
                       dp[bi][bj][ci][cj] = path(bi+1, bj, ci-1, cj) +
                                            path(bi+1, bj, ci, cj-1) +
                                            path(bi, bj+1, ci-1, cj) +
                                            path(bi, bj+1, ci, cj-1)

So, we have finished writing algorithm for our problem. Let’s write a beautiful code for this beautiful algorithm:

 

#include <bits/stdc++.h>

using namespace std;

#define N 3
#define M 4

int dp[N+1][M+1][N+1][M+1];
string S[N];

int path(int bi, int bj, int ci, int cj)
{
    if (bi>ci || bj>cj || S[bi-1][bj-1] != S[ci-1][cj-1]) return 0;

    if (abs(bi-ci) + abs(bj-cj) == 1) return 1;

    if (dp[bi][bj][ci][cj] != -1) return dp[bi][bj][ci][cj];

    return dp[bi][bj][ci][cj] = path(bi+1, bj, ci-1, cj) +
                                path(bi+1, bj, ci, cj-1) +
                                path(bi, bj+1, ci-1, cj) +
                                path(bi, bj+1, ci, cj-1);

}

int main()
{
    
    S[0] = "aaab", S[1] = "baaa", S[2] = "abba";
    memset(dp, -1, sizeof(dp));
    
    path(1, 1, N, M);
    
    cout << dp[1][1][N][M] << endl;

    // output is 3
    
    return 0;
}

Finally we have solved “Number of Palindromic paths in a Matrix” with time and space complexity O(N*M*N*M). As you can see that we are using too much memory and we can still optimize it slightly more. Clearly we are not storing data for bi > bj and ci > cj and hence, our memory is getting wasted. One idea to avoid this wastage is to use map for storing data. But this will increase time complexity by a factor of log(N*M*N*M). If you have any more doubts, then, you can refer to video tutorial for this problem.

So, that’s it guys for today. I hope you would have found this tutorial insightful. If you like reading my tutorials, then, please follow my blog and share it with your friends. Meanwhile, don’t forget to solve CLCO02.
You can subscribe to my YouTube channel for video tutorials on dynamic programming.
You can connect with me on LinkedIn. To get all of your queries answered, you can message me on Quora. Follow me on medium for more of my writings.

Leave a Reply

%d bloggers like this: