Find length of the longest consecutive path from a given starting character | tool matrices to recur for adjacent cells . ; dp [ i ] [ j ] Stores length of longest consecutive path starting at arr [ i ] [ j ] . ; check whether mat [ i ] [ j ] is a valid cell or not . ; Check whether current character is adjacent to previous character ( character processed in parent call ) or not . ; i , j are the indices of the current cell and prev is the character processed in the parent call . . also mat [ i ] [ j ] is our current character . ; If this cell is not valid or current character is not adjacent to previous one ( e . g . d is not adjacent to b ) or if this cell is already included in the path than return 0. ; If this subproblem is already solved , return the answer ; Initialize answer ; recur for paths with different adjacent cells and store the length of longest path . ; save the answer and return ; Returns length of the longest path with all characters consecutive to each other . This function first initializes dp array that is used to store results of subproblems , then it calls recursive DFS based function getLenUtil ( ) to find max length path ; check for each possible starting point ; recur for all eight adjacent cells ; Driver program
let x = [ 0 , 1 , 1 , - 1 , 1 , 0 , - 1 , - 1 ] ; let y = [ 1 , 0 , 1 , 1 , - 1 , - 1 , 0 , - 1 ] ; let R = 3 ; let C = 3 ; let dp = new Array ( R ) ; for ( let i = 0 ; i < R ; i ++ ) { dp [ i ] = new Array ( C ) ; for ( let j = 0 ; j < C ; j ++ ) { dp [ i ] [ j ] = 0 ; } } function isvalid ( i , j ) { if ( i < 0 j < 0 i >= R j >= C ) return false ; return true ; } function isadjacent ( prev , curr ) { return ( ( curr . charCodeAt ( ) - prev . charCodeAt ( ) ) == 1 ) ; } function getLenUtil ( mat , i , j , prev ) { if ( ! isvalid ( i , j ) || ! isadjacent ( prev , mat [ i ] [ j ] ) ) return 0 ; if ( dp [ i ] [ j ] != - 1 ) return dp [ i ] [ j ] ; let ans = 0 ; for ( let k = 0 ; k < 8 ; k ++ ) ans = Math . max ( ans , 1 + getLenUtil ( mat , i + x [ k ] , j + y [ k ] , mat [ i ] [ j ] ) ) ; return dp [ i ] [ j ] = ans ; } function getLen ( mat , s ) { for ( let i = 0 ; i < R ; ++ i ) for ( let j = 0 ; j < C ; ++ j ) dp [ i ] [ j ] = - 1 ; let ans = 0 ; for ( let i = 0 ; i < R ; i ++ ) { for ( let j = 0 ; j < C ; j ++ ) { if ( mat [ i ] [ j ] == s ) { for ( let k = 0 ; k < 8 ; k ++ ) ans = Math . max ( ans , 1 + getLenUtil ( mat , i + x [ k ] , j + y [ k ] , s ) ) ; } } } return ans ; } let mat = [ [ ' ' , ' ' , ' ' ] , [ ' ' , ' ' , ' ' ] , [ ' ' , ' ' , ' ' ] ] ; document . write ( getLen ( mat , ' ' ) + " " ) ; document . write ( getLen ( mat , ' ' ) + " " ) ; document . write ( getLen ( mat , ' ' ) + " " ) ; document . write ( getLen ( mat , ' ' ) ) ;