Minimum moves to reach from i to j in a cyclic string | Function to return the count of steps required to move from i to j ; Starting from i + 1 ; Count of steps ; Current character ; If current character is different from previous ; Increment steps ; Update current character ; Return total steps ; Function to return the minimum number of steps required to reach j from i ; Swap the values so that i <= j ; Steps to go from i to j ( left to right ) ; While going from i to j ( right to left ) First go from i to 0 then from ( n - 1 ) to j ; If first and last character is different then it 'll add a step to stepsToLeft ; Return the minimum of two paths ; Driver code
def getSteps ( str , i , j , n ) : NEW_LINE INDENT k = i + 1 NEW_LINE steps = 0 NEW_LINE ch = str [ i ] NEW_LINE while ( k <= j ) : NEW_LINE INDENT if ( str [ k ] != ch ) : NEW_LINE INDENT steps = steps + 1 NEW_LINE ch = str [ k ] NEW_LINE DEDENT k = k + 1 NEW_LINE DEDENT return steps NEW_LINE DEDENT def getMinSteps ( str , i , j , n ) : NEW_LINE INDENT if ( j < i ) : NEW_LINE INDENT temp = i NEW_LINE i = j NEW_LINE j = temp NEW_LINE DEDENT stepsToRight = getSteps ( str , i , j , n ) NEW_LINE stepsToLeft = getSteps ( str , 0 , i , n ) + getSteps ( str , j , n - 1 , n ) NEW_LINE if ( str [ 0 ] != str [ n - 1 ] ) : NEW_LINE INDENT stepsToLeft = stepsToLeft + 1 NEW_LINE DEDENT return min ( stepsToLeft , stepsToRight ) NEW_LINE DEDENT str = " SSNSS " NEW_LINE n = len ( str ) NEW_LINE i = 0 NEW_LINE j = 3 NEW_LINE print ( getMinSteps ( str , i , j , n ) ) NEW_LINE