Question 4 – Palindromic Paths

November 23, 2021

Palindromic Paths

Here, in this page we will discuss one of the problem Palindromic Paths that was asked in InfyTQ Advance Coding Section. We will discuss the problem description along with function description, Test Cases along with there explanation.

You will find the solution of the problem in different programming language.

Palindromic Paths

Problem Statement-:

You are given a grid of size of N*M (1-based indexing). Each cell in the grid contains a lower case English alphabet (a-z). You have to replace some letters of the grid such that any path from (1,1) to (N,M) is a palindromic path. A path is palindromic if the string obtained by joining letters from the corresponding cells of a traversed path is a palindrome i.e. reads the same forward and backward. You are only allowed to move Right or Down in the grid.

Calculate the minimum number of letters that you need to replace such that any valid path from (1,1) to (N,M) is palindromic.

Function Description:

Complete the palindromicPaths function in the editor below. It has the following parameter(s):

Parameters:

Name	Type	Description
n	Integer	Number of rows in the grid
m	Integer	number of columns in the grid
grid	string 2D array	the given grid

Return: The function must return an integer denoting the minimum number of letters.

Constraints:

1 <= N <= 10^3
1 <= M <= 10^3
a <= grid[i][j] <= z

Input format for Custom Testing:

The first line contains an integer, N, denoting the number of rows in the grid.
The next line contains an integer, M, denoting the number of columns in the grid.
Each line i of the N subsequent lines (where 0 <= i <N) contains a string of lower-case English Alphabets of size M.

Sample Test Cases

Sample Input
2
2
ac
bc
Sample Output
1
Explanation
Change the letter at (2,2) to ‘a’, such that both paths become palindromes.
Path1: (1,1) -> (1,2) -> (2,2)
Path2: (1,1) -> (2,1) -> (2,2)

C++

Python

C++

#include <bits/stdc++.h>
using namespace std;
 
int func(vector<vector<int>> mat)
{
    int ans=0;
    int n=mat.size(),m=mat[0].size();
    map<int,map<int,int>> mp;
    for(int i=0;i<n;i++)
    for(int j=0;j<m;j++)
    {
        int ind =i+j;
        mp[ind][mat[i][j]]++;
    }
 
    int r=m+n-2,l=0;
    while(l<r)
    {
        int t=0,mx=0;
        for(auto x:mp[r])
        {
            mp[l][x.first]+=x.second;
        }
        for(auto x:mp[l])
        {
            t+=x.second;
            mx=max(x.second,mx);
        }
        ans+=t-mx;
        l++;
        r--;
    }
    return ans;
}
 
int main()
{
    int N,M;
    string s;
    cin>>N>>M;
    vector<vector<int>> mat(N,vector<int>(M));
    for(int i=0;i<N;i++)
    {
        cin>>s;
        for(int j=0;j<M;j++)
        mat[i][j]=s[j]-'a';
    }
    cout<<func(mat);
 
}

Python

def m(lis,n):
    d1=dict()
    for i in lis:
        if i in d1:
            d1[i]+=1

        else:
            d1[i]=1

    m1=0
    for i in d1:
        m1=max(m1,d1[i])

    return (n-m1)

r=int(input())
c=int(input())
a=[]
for i in range(r):
    b=list(input())
    a.append(b)

d=dict()

t=r+c-2
d=dict()
for i in range(r):
    for j in range(c):
        t1=min((i+j),(t-(i+j)))
        if t1 in d:
            d[t1].append(a[i][j])

        else:
            d[t1]=[a[i][j]]

ans=0
for i in d:
    if (i*2)!=t:
        lis=d[i]
        n=len(d[i])
        ans+=m(lis,n)

print(ans)