Find minimum number of steps to reach the end of String | Java implementation of the approach ; 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 valiINT_MAXd 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
class GFG { final static int INT_MAX = Integer . MAX_VALUE ; static int minSteps ( String str , int n , int k ) { if ( str . charAt ( n - 1 ) == '0' ) return - 1 ; if ( n == 1 ) return 0 ; if ( n < 4 ) return 1 ; int dp [ ] = new int [ n ] ; dp [ n - 1 ] = 0 ; dp [ n - 2 ] = 1 ; dp [ n - 3 ] = 1 ; for ( int i = n - 4 ; i >= 0 ; i -- ) { if ( str . charAt ( i ) == '0' ) continue ; int steps = INT_MAX ; if ( i + k < n && str . charAt ( i + k ) == '1' ) steps = Math . min ( steps , dp [ i + k ] ) ; if ( str . charAt ( i + 1 ) == '1' ) steps = Math . min ( steps , dp [ i + 1 ] ) ; if ( str . charAt ( i + 2 ) == '1' ) steps = Math . min ( steps , dp [ i + 2 ] ) ; dp [ i ] = ( steps == INT_MAX ) ? steps : 1 + steps ; } if ( dp [ 0 ] == INT_MAX ) return - 1 ; return dp [ 0 ] ; } public static void main ( String [ ] args ) { String str = "101000011" ; int n = str . length ( ) ; int k = 5 ; System . out . println ( minSteps ( str , n , k ) ) ; } }