Find minimum number of steps to reach the end of String | Function to return the minimum number of steps to reach the end ; If the end can 't be reached ; Already at the end ; If the length is 2 or 3 then the end can be reached in a single step ; For the other cases , solve the problem using dynamic programming ; It requires no move from the end to reach the end ; From the 2 nd last and the 3 rd last index , only a single move is required ; Update the answer for every index ; If the current index is not reachable ; To store the minimum steps required from the current index ; If it is a valid move then update the minimum steps required ; Update the minimum steps required starting from the current index ; Cannot reach the end starting from str [ 0 ] ; Return the minimum steps required ; Driver code
function minSteps ( str , n , k ) { if ( str [ n - 1 ] == ' ' ) return - 1 ; if ( n == 1 ) return 0 ; if ( n < 4 ) return 1 ; var dp = Array ( n ) ; dp [ n - 1 ] = 0 ; dp [ n - 2 ] = 1 ; dp [ n - 3 ] = 1 ; for ( var i = n - 4 ; i >= 0 ; i -- ) { if ( str [ i ] == ' ' ) continue ; var steps = 1000000000 ; if ( i + k < n && str [ i + k ] == ' ' ) steps = Math . min ( steps , dp [ i + k ] ) ; if ( str [ i + 1 ] == ' ' ) steps = Math . min ( steps , dp [ i + 1 ] ) ; if ( str [ i + 2 ] == ' ' ) steps = Math . min ( steps , dp [ i + 2 ] ) ; dp [ i ] = ( steps == 1000000000 ) ? steps : 1 + steps ; } if ( dp [ 0 ] == 1000000000 ) return - 1 ; return dp [ 0 ] ; } var str = " " ; var n = str . length ; var k = 5 ; document . write ( minSteps ( str , n , k ) ) ;