Consecutive Characters

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
4 upvotes
Asked in companies
Urban Company (UrbanClap)Goldman SachsInfo Edge India (Naukri.com)

Problem statement

You are given a matrix of 'N' rows and 'M' columns consisting of lowercase characters. You are provided with a string ‘STR,’ and your task is to find the length of the longest consecutive character path for each character in the string ‘STR’. All characters in the path are consecutive, i.e., every character in the path is next to the previous character in alphabetical order. It is allowed to move in all 8 adjacent directions from a cell.

Note: 
Suppose you are at position (x, y) then you can move to : [ (x + 1 , y ), ( x - 1 , y ), ( x , y + 1), (x , y - 1), (x + 1, y + 1), (x + 1, y - 1), (x - 1, y + 1), (x - 1, y - 1) ].
For Example: 
If ‘N’ = 2, ‘M’ = 2, 'STR’ = "a" and the input matrix is 
[ [ ab ]
  [ ed ] ] 
We need to find the maximum length of the path from starting character ’a’. So the maximum length is 2, which is [a, b]. Hence, the answer is [2].
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains a single integer 'T' representing the number of test cases.

The first line of each test case contains two integers, ‘N’ and ‘M’, denoting the number of rows and columns of the character array ‘matrix’.

The next ‘N’ lines of each test case contain a string consisting of ‘M’ characters denoting the elements of the array 'matrix'.

The last line of each test case contains the string ‘STR‘, which contains starting characters(without space).
Output Format : 
For each test case, print the space-separated array of integers where each integer is the length of the longest path from the character at that index in the string ‘STR’.

Print the output of each test case in a separate line.
Note: 
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 10
1 <= M <= 300
1 <= N <= 300
‘a’ <= matrix[i][j], STR[i] <= ‘z’    
1 <= |STR[i]| <= 26     

Time Limit: 1 sec
Sample Input 1:
2
2 3
aef
pbc
ba
4 5
abcde
udjfi
mtgna
kunyq
afm
Sample Output 1:
2 3    
7 2 1
Explanation:
In test case 1:
There is a matrix of characters with ‘N’ = 2 and ‘M’ = 3. 
The length of the path with ‘b’ as starting character is 2, which is [b, c]. 
The length of the path with ‘a’ as the starting character is 3, which is [a, b, c] 
Hence, the answer is [2, 3]. 

In test case 2:
There is a matrix of characters with ‘N’ = 4 and ‘M’ = 5. 
The length of the path with  ‘a’ as the starting character is 7, which is [a, b, c, d, e, f].
The length of the path with ‘f’ as the starting character is 2, which is [f, g].
The length of the path with ‘m’ as the starting character is 1, which is [m] 
Hence, the answer is [7, 2, 1].
Sample Input 2:
2
2 4
aefg
pbcd
ec
3 2
ab
cd
ef
a
Sample Output 2:
3 2
6
Hint

Try to think of a recursive solution.

Approaches (2)
Recursive Approach

In this approach, we are going to implement a recursive function. We will traverse the array matrix for each character of STR as a starting character. We will check if matrix[i][j] is equal to STR[index] then, we will create a function call to find the longest path. 

  1. We will create a recursive call on all 8 sides to find the next consecutive character in the function. We have to maintain a variable maximumLength to store the maximum length returned from all 8 sides.
  2. In the end, we will return (1 + maximumLength) from the function representing the longest path.

 

Algorithm:

  • Make a recursive function recFunction(currRow, currCol, matrix, charToFind, N, M). This function returns the length of the string using charToFind as starting character from given indexes.
  • The base condition of this function is if matrix[currRow][currCol] is not equal to charToFind in this case return 0.
  • Initialize a maximumLength variable with 0, which maintains the length of the maximum length string.
  • Maintain an array adjCells with values as [[1, 1] , [1, 0] , [1, -1] , [0, 1] , [0 , -1] , [-1, 1] , [-1, 0] , [-1, -1] ]
  • Iterate i over all the elements of adjCells array.  
    • Set newRow as sum of currRow and adjCells[i][0].
    • Set newCol as sum of currCol and adjCells[i][1].
    • If that newRow and newCol is in the index range, then call a recursive function recFunction(newRow ,newCol ,matrix , charToFind + 1,  N,  M) and store the obtained length in the variable currLength.
    • If currLength is greater than maximumLength then update maximumLength variable with currLength.
  • Return maximumLength + 1, which is the required maximum length using charToFind as starting character.
  • Make a longestLengthString(matrix, N, M, STR) function that returns the array of integers of maximum lengths using characters given in STR as the starting characters.
    • Create an empty array result of the size length of STR.
    • Traverse index from 0 to length of STR - 1 
      • Initialize a maximumLength variable with 0.
      • Iterate over all the matrix elements if STR[index] is found, then call recFunction.
      • If the obtained length returned by the above function call is greater than maximumLength then set maximumLength as length returned by the above function call.
      • Set result[index] as maximumLength.
    • Return result array.
Time Complexity

O((N*M)^2 * (length of STR)) where N and M are the numbers of rows and columns in the array matrix, and STR is the given string. 

 

We will traverse through STR that takes O(length of STR) time. For each iteration, we will traverse through the character array that takes O(N*M) time, and also, for each element of the array, we call the recursive function that takes O(N*M) time. Hence, the overall time complexity is O((N*M)^2 * (length of STR)). 

Space Complexity

O(N*M) where N and M are the numbers of rows and columns in the array matrix.

 

The space complexity O(N*M) is required for the recursion stack in the worst case. Hence, the overall space needed is O(N*M).

Code Solution
(100% EXP penalty)
Consecutive Characters
Full screen
Console