Longest sub | Javascript implementation of the approach ; Function to return the length of the largest sub - string divisible by 3 ; Base - case ; If the state has been solved before then return its value ; Marking the state as solved ; Recurrence relation ; Driver code
var N = 100 var dp = Array . from ( Array ( N ) , ( ) => Array ( 3 ) ) ; var v = Array . from ( Array ( N ) , ( ) => Array ( 3 ) ) ; function findLargestString ( s , i , r ) { if ( i == s . length ) { if ( r == 0 ) return 0 ; else return - 1000000000 ; } if ( v [ i ] [ r ] ) return dp [ i ] [ r ] ; v [ i ] [ r ] = 1 ; dp [ i ] [ r ] = Math . max ( 1 + findLargestString ( s , i + 1 , ( r * 2 + ( s [ i ] . charCodeAt ( 0 ) - ' ' . charCodeAt ( 0 ) ) ) % 3 ) , findLargestString ( s , i + 1 , r ) ) ; return dp [ i ] [ r ] ; } var s = " " ; document . write ( findLargestString ( s , 0 , 0 ) ) ;