Last Updated: 12 Dec, 2020
Consecutive Characters
Moderate
Asked in companies
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].
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
Approaches
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.
- 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.
- 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.
As we have discussed in the previous approach, we will create a recursive function to find the longest path. This approach will maintain a dynamic array dpMatrix that stores the maximum length using the character present at that index in the matrix as starting character. This helps to remove the repetitive tasks and reduces the time complexity.
Algorithm:
- Make a function getLength(matrix, currRow, currCol, charToFind, N, M, dpMatrix) which returns the length of the maximum length string using charToFind as starting character from this index.
- The base condition of this function is if matrix[currRow][currCol] is not equal to charToFind in this case return 0.
- If dpMatrix[currRow][currCol] is not equal to -1 then return dpMatrix[currRow][currCol].
- 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 the 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 getLength(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.
- Set dpMatrix[currRow][currCol] as maximumLength + 1.
- Return maximumLength + 1, which is the required maximum length using charToFind as starting character.
- Create a longestLengthString(matrix, STR, N, M) 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.
- Make 2d array dpMatrix of size N rows and M columns and initialize all its cells with -1.
- Iterate index from 0 to length of STR - 1
- Initialize a maximumLength variable with 0.
- Iterate over all the elements of the matrix if STR[index] is found, then call getLength function.
- 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.
Similar problems