Consecutive Characters
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

Question

Consecutive Characters

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

Accepted Answer

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.

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.

Space Complexity: O(1)Explanation:

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).

Time Complexity: OtherExplanation:

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)).

C++ (g++ 5.4)

/*

Time Complexity : 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, and STR is the given string. 

*/



int recFunction(int currRow, int currCol, vector &matrix, char charToFind, int n, int m)

{    

    if(matrix[currRow][currCol] != charToFind)

    {

        return 0;

    }



    // Variable to maintain maximum length

    int maximumLength = 0;



    // Array to traverse to 8 adjacent vertices

    vector> adjCells = {{1, 1}, {1, 0}, {1, -1}, {0, 1}, 

                    {0, -1}, {-1, 1}, {-1, 0}, {-1, -1}};



    for(int i = 0; i < 8; i++)

    {

        // Calculating the new row and new column

        int newRow = currRow + adjCells[i][0];

        int newCol = currCol + adjCells[i][1];



        // If new indexes is in index range of the matrix

        if( newRow >= 0 && newRow < n && newCol >= 0 && newCol < m)

        {



            char temp = charToFind + 1;

            int currLength = recFunction(newRow, newCol, matrix, temp, n, m);

            maximumLength = max(maximumLength, currLength);

        }

    }



    return (maximumLength + 1);

}





vector longestLengthString(vector &matrix, int n, int m, string &str)

{

    // Maintain a result array

    vector result(str.size());



    // Traverse through the string str

    for(int index = 0; index < str.size(); index++)

    {

        int maximumLength = 0;

        

        for(int i = 0; i < n; i++)

        {   

            for(int j = 0; j < m; j++)

            {    

                if(matrix[i][j] == str[index])

                {

                    int currLength = recFunction(i, j, matrix, str[index], n, m);

                    maximumLength = max(maximumLength, currLength);

                }

            }

        }



        result[index] = maximumLength;

    }



    // Return the result array

    return result;

}

Python (3.5)

"""

Time Complexity : 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, and STR is the given string. 

"""



def recFunction(currRow, currCol, matrix, charToFind, n, m):

    

    if(matrix[currRow][currCol] != charToFind):

        return 0



    # Variable to maintain maximum length

    maximumLength = 0



    # Array to traverse to 8 adjacent vertices

    adjCells = [[1, 1], [1, 0], [1, -1], [0, 1], 

                [0, -1], [-1, 1], [-1, 0], [-1, -1]]



    for i in range(8):



        # Calculating the new row and new column

        newRow = currRow + adjCells[i][0]

        newCol = currCol + adjCells[i][1]



        # If new indexes is in index range of the matrix

        if( newRow >= 0 and newRow < n and newCol >= 0 and newCol < m):



            temp = chr(ord(charToFind) + 1)

            currLength = recFunction(newRow, newCol, matrix, temp, n, m)

            maximumLength = max(maximumLength, currLength)



    return (maximumLength + 1)





def longestLengthString(matrix, n, m, str):



    # Maintain a result array

    result = [0 for i in range(len(str))]



    # Traverse through the string str

    for index in range(0, len(str)):



        maximumLength = 0

        

        for i in range(0, n):

            

            for j in range(0, m):

                

                if(matrix[i][j] == str[index]):

                    currLength = recFunction(i, j, matrix, str[index], n, m)

                    maximumLength = max(maximumLength, currLength)



        result[index] = maximumLength



    # Return the result array

    return result

Java (SE 1.8)


/*
	Time Complexity : 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, and STR is the given string. 
*/
public class Solution {
	private static int recFunction(int currRow, int currCol, String[] matrix, char charToFind, int n, int m) {
		if (matrix[currRow].charAt(currCol) != charToFind) {
			return 0;
		}

		// Variable to maintain maximum length
		int maximumLength = 0;

		// Array to traverse to 8 adjacent vertices
		int[][] adjCells = { { 1, 1 }, { 1, 0 }, { 1, -1 }, { 0, 1 }, { 0, -1 }, { -1, 1 }, { -1, 0 }, { -1, -1 } };

		for (int i = 0; i < 8; i++) {
			
			// Calculating the new row and new column
			int newRow = currRow + adjCells[i][0];
			int newCol = currCol + adjCells[i][1];

			// If new indexes is in index range of the matrix
			if (newRow >= 0 && newRow < n && newCol >= 0 && newCol < m) {

				char temp = (char) (charToFind + 1);
				int currLength = recFunction(newRow, newCol, matrix, temp, n, m);
				maximumLength = Math.max(maximumLength, currLength);
			}
		}

		return (maximumLength + 1);

	}

	public static int[] longestLengthString(String[] matrix, int n, int m, String str) {

		// Maintain a result array
		int result[] = new int[str.length()];

		// Traverse through the string str
		for (int index = 0; index < str.length(); index++) {
			int maximumLength = 0;

			for (int i = 0; i < n; i++) {
				for (int j = 0; j < m; j++) {
					if (matrix[i].charAt(j) == str.charAt(index)) {
						int currLength = recFunction(i, j, matrix, str.charAt(index), n, m);
						maximumLength = Math.max(maximumLength, currLength);
					}
				}
			}

			result[index] = maximumLength;
		}

		// Return the result array
		return result;
	}

}

Accepted Answer

Dynamic Programming

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.

Space Complexity: OtherExplanation:

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 needed to make a dynamic array. 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).

Time Complexity: OtherExplanation:

O(N*M* (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 are traversing the complete input array matrix that takes O(N*M) time for each character of STR. Hence, the overall time complexity is O(N*M* (length of STR)).

Python (3.5)

"""

Time Complexity : O(N*M* (length of STR))

Space Complexity : O(N*M)



where N and M are the numbers of rows and columns in the array matrix, and STR is the given string. 

"""





def getLength(matrix, currRow, currCol, charToFind, n, m, dpMatrix):

    

    if (matrix[currRow][currCol] != charToFind):

        return 0



    # If we had already visited that cell then directly return from it

    if (dpMatrix[currRow][currCol] != -1):

        return dpMatrix[currRow][currCol]



    # Variable to maintain the maximum length

    maximumLength = 0



    # Array to traverse 8 adjacent cells

    adjCells = [[1, 1], [1, 0], [1, -1], [0, 1],

                [0, -1], [-1, 1], [-1, 0], [-1, -1]]



    for i in range(8):



        # Calculate new row and new column number

        newRow = currRow + adjCells[i][0]

        newCol = currCol + adjCells[i][1]



        if(newRow >= 0 and newRow < n and newCol >= 0 and newCol < m):



            # Find next consecutive character

            temp = chr(ord(charToFind) + 1)

            currLength = getLength(matrix, newRow, newCol, temp, n, m, dpMatrix)

            maximumLength = max(maximumLength, currLength)



    # Store the maximum length in dpMatrix array

    dpMatrix[currRow][currCol] = maximumLength + 1



    # Return the maximum length

    return (maximumLength + 1)





def longestLengthString(matrix, n, m, str):



    # Maintain the result array

    result = [0 for i in range(len(str))] 



    dpMatrix = [[-1 for j in range(m)] for i in range(n)]



    # Traverse through the string str

    for index in range(0, len(str)):



        maximumLength = 0



        for i in range(0, n):

            

            for j in range(0, m):

                

                if (matrix[i][j] == str[index]):

                    currLength = getLength(matrix, i, j, str[index], n, m, dpMatrix)

                    maximumLength = max(maximumLength,currLength)



        result[index] = maximumLength



    # Return result array

    return result

C++ (g++ 5.4)

/*

Time Complexity : O(N*M* (length of STR))

Space Complexity : O(N*M)



where N and M are the numbers of rows and columns in the array matrix, and STR is the given string. 

*/



int getLength(vector &matrix, int currRow, int currCol, char charToFind, 

                int n, int m, vector> &dpMatrix)

{   

    if (matrix[currRow][currCol] != charToFind)

    {

        return 0;

    }



    // If we had already visited that cell then directly return from it

    if (dpMatrix[currRow][currCol] != -1)

    {

        return dpMatrix[currRow][currCol];

    }



    // Variable to maintain the maximum length

    int maximumLength = 0;



    // Array to traverse 8 adjacent cells

    vector> adjCells = {{1, 1}, {1, 0}, {1, -1}, {0, 1},

                {0, -1}, {-1, 1}, {-1, 0}, {-1, -1}};



    for(int i = 0; i < 8; i++)

    {

        // Calculate new row and new column number

        int newRow = currRow + adjCells[i][0];

        int newCol = currCol + adjCells[i][1];



        if(newRow >= 0 && newRow < n && newCol >= 0 && newCol < m)

        {

            // Find next consecutive character

            char temp = charToFind + 1;

            int currLength = getLength(matrix, newRow, newCol, temp, n, m, dpMatrix);

            maximumLength = max(maximumLength, currLength);

        }

    }



    // Store the maximum length in dpMatrix array

    dpMatrix[currRow][currCol] = maximumLength + 1;



    // Return the maximum length

    return (maximumLength + 1);

}





vector longestLengthString(vector &matrix, int n, int m, string &str)

{

    // Maintain the result array

    vector result(str.size(), 0); 



    vector> dpMatrix(n,vector(m, -1));



    // Traverse through the string str

    for(int index = 0; index < str.size(); index++)

    {

        int maximumLength = 0;



        for(int i = 0; i < n; i++)

        {   

            for(int j = 0; j < m; j++) 

            {   

                if (matrix[i][j] == str[index])

                {

                    int currLength = getLength(matrix, i, j, str[index], n, m, dpMatrix);

                    maximumLength = max(maximumLength,currLength);

                }

            }

        }



        result[index] = maximumLength;

    }



    // Return result array

    return result;

}

Java (SE 1.8)


/*
	Time Complexity : O(N*M* (length of STR))
	Space Complexity : O(N*M)
	
	where N and M are the numbers of rows and columns in the array matrix, and STR is the given string. 
*/
import java.util.Arrays;

public class Solution {
	public static int getLength(String[] matrix, int currRow, int currCol, char charToFind, int n, int m,
			int[][] dpMatrix) {
		if (matrix[currRow].charAt(currCol) != charToFind) {
			return 0;
		}

		// If we had already visited that cell then directly return from it
		if (dpMatrix[currRow][currCol] != -1) {
			return dpMatrix[currRow][currCol];
		}

		// Variable to maintain the maximum length
		int maximumLength = 0;

		// Array to traverse 8 adjacent cells
		int[][] adjCells = { { 1, 1 }, { 1, 0 }, { 1, -1 }, { 0, 1 }, { 0, -1 }, { -1, 1 }, { -1, 0 }, { -1, -1 } };

		for (int i = 0; i < 8; i++) {
			
			// Calculate new row and new column number
			int newRow = currRow + adjCells[i][0];
			int newCol = currCol + adjCells[i][1];

			if (newRow >= 0 && newRow < n && newCol >= 0 && newCol < m) {
				// Find next consecutive character
				char temp = (char) (charToFind + 1);
				int currLength = getLength(matrix, newRow, newCol, temp, n, m, dpMatrix);
				maximumLength = Math.max(maximumLength, currLength);
			}
		}

		// Store the maximum length in dpMatrix array
		dpMatrix[currRow][currCol] = maximumLength + 1;

		// Return the maximum length
		return (maximumLength + 1);
	}

	public static int[] longestLengthString(String[] matrix, int n, int m, String str) {

		// Maintain the result array
		int[] result = new int[str.length()];

		int dpMatrix[][] = new int[n][m];
		for (int i = 0; i < n; i++) {
			int[] temp = new int[m];
			Arrays.fill(temp, -1);
			dpMatrix[i] = temp;
		}

		// Traverse through the string str
		for (int index = 0; index < str.length(); index++) {
			int maximumLength = 0;

			for (int i = 0; i < n; i++) {
				for (int j = 0; j < m; j++) {
					if (matrix[i].charAt(j) == str.charAt(index)) {
						int currLength = getLength(matrix, i, j, str.charAt(index), n, m, dpMatrix);
						maximumLength = Math.max(maximumLength, currLength);
					}
				}
			}

			result[index] = maximumLength;
		}

		// Return result array
		return result;
	}

}

Accepted Answer

good

Note:

For Example:

Input Format :

Output Format :

Note:

Constraints :

Top Info Edge Test Engineer interview questions & answers

Popular interview questions of Test Engineer