Minimum circular rotations to obtain a given numeric string by avoiding a set of given strings | Java Program to count the minimum number of circular rotations required to obtain a given numeric Strings avoiding a set of blocked Strings ; to be avoided If the starting String needs ; to be avoided If the final String needs ; Variable to store count of rotations ; BFS Approach ; of the queue Store the current size ; Traverse the String ; current character Increase the ; Circular rotation ; If target is reached ; If the String formed is not one to be avoided ; Add it to the list of Strings to be avoided to prevent visiting already visited states ; Decrease the current value by 1 and repeat the similar checkings ; Restore the original character ; Driver code
import java . util . ArrayList ; import java . util . Arrays ; import java . util . HashSet ; import java . util . LinkedList ; import java . util . Queue ; class GFG { static int minCircularRotations ( String target , ArrayList < String > blocked , int N ) { String start = " " ; for ( int i = 0 ; i < N ; i ++ ) { start += '0' ; } HashSet < String > avoid = new HashSet < > ( ) ; for ( int i = 0 ; i < blocked . size ( ) ; i ++ ) avoid . add ( blocked . get ( i ) ) ; if ( avoid . contains ( start ) ) return - 1 ; if ( avoid . contains ( target ) ) return - 1 ; Queue < String > qu = new LinkedList < > ( ) ; qu . add ( start ) ; int count = 0 ; while ( ! qu . isEmpty ( ) ) { count ++ ; int size = qu . size ( ) ; for ( int j = 0 ; j < size ; j ++ ) { StringBuilder st = new StringBuilder ( qu . poll ( ) ) ; for ( int i = 0 ; i < N ; i ++ ) { char ch = st . charAt ( i ) ; st . setCharAt ( i , ( char ) ( st . charAt ( i ) + 1 ) ) ; if ( st . charAt ( i ) > '9' ) st . setCharAt ( i , '0' ) ; if ( st . toString ( ) . equals ( target ) ) return count ; if ( ! avoid . contains ( st . toString ( ) ) ) qu . add ( st . toString ( ) ) ; avoid . add ( st . toString ( ) ) ; st . setCharAt ( i , ( char ) ( ch - 1 ) ) ; if ( st . charAt ( i ) < '0' ) st . setCharAt ( i , '9' ) ; if ( st . toString ( ) . equals ( target ) ) return count ; if ( ! avoid . contains ( st . toString ( ) ) ) qu . add ( st . toString ( ) ) ; avoid . add ( st . toString ( ) ) ; st . setCharAt ( i , ch ) ; } } } return - 1 ; } public static void main ( String [ ] args ) { int N = 4 ; String target = "7531" ; ArrayList < String > blocked = new ArrayList < > ( Arrays . asList ( "1543" , "7434" , "7300" , "7321" , "2427" ) ) ; System . out . println ( minCircularRotations ( target , blocked , N ) ) ; } }