InfyTQ Advantage Round Python Coding Questions & Answer 2022 - Palindromic Paths

 

InfyTQ Advantage Round Python Coding Questions

& Answer 2022

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)

 

Program :

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("Number of Rows in Grid : "))

c=int(input("Number of Columns in Grid : "))

a=[]

for i in range(r):

    b=list(input("\tString (LowerCase) : "))

    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("\nMinimum Number Of Letters : ",ans)

 

for execution and output so check the video :