Convert a Binary String to another by flipping prefixes minimum number of times | C ++ program for the above approach ; Function to count minimum number of operations required to convert string a to another string b ; Store the lengths of each prefixes selected ; Traverse the string ; If first character is same as b [ i ] ; Insert 1 to ops [ ] ; And , flip the bit ; Reverse the prefix string of length i + 1 ; Flip the characters in this prefix length ; Push ( i + 1 ) to array ops [ ] ; Print the number of operations ; Print the length of each prefixes stored ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; void minOperations ( string a , string b , int n ) { vector < int > ops ; for ( int i = n - 1 ; i >= 0 ; i -- ) { if ( a [ i ] != b [ i ] ) { if ( a [ 0 ] == b [ i ] ) { ops . push_back ( 1 ) ; a [ 0 ] = '0' + ! ( a [ 0 ] - '0' ) ; } reverse ( a . begin ( ) , a . begin ( ) + i + 1 ) ; for ( int j = 0 ; j <= i ; j ++ ) { a [ j ] = '0' + ! ( a [ j ] - '0' ) ; } ops . push_back ( i + 1 ) ; } } cout << ops . size ( ) << " STRNEWLINE " ; for ( int x : ops ) { cout << x << ' ▁ ' ; } } int main ( ) { string a = "10" , b = "01" ; int N = a . size ( ) ; minOperations ( a , b , N ) ; return 0 ; }