text: Minimum Swaps for Bracket Balancing | C ++ program to count swaps required to balance string ; Function to calculate swaps required ; Keep track of ' [ ' ; To count number of encountered ' [ ' ; To track position of next ' [ ' in pos ; To store result ; Increment count and move p to next position ; We have encountered an unbalanced part of string ; Increment sum by number of swaps required i . e . position of next ' [ ' - current position ; Reset count to 1 ; Driver code
code: #include <iostream> NEW_LINE #include <vector> NEW_LINE #include <algorithm> NEW_LINE using namespace std ; long swapCount ( string s ) { vector < int > pos ; for ( int i = 0 ; i < s . length ( ) ; ++ i ) if ( s [ i ] == ' [ ' ) pos . push_back ( i ) ; int count = 0 ; int p = 0 ; long sum = 0 ; for ( int i = 0 ; i < s . length ( ) ; ++ i ) { if ( s [ i ] == ' [ ' ) { ++ count ; ++ p ; } else if ( s [ i ] == ' ] ' ) -- count ; if ( count < 0 ) { sum += pos [ p ] - i ; swap ( s [ i ] , s [ pos [ p ] ] ) ; ++ p ; count = 1 ; } } return sum ; } int main ( ) { string s = " [ ] ] [ ] [ " ; cout << swapCount ( s ) << " STRNEWLINE " ; s = " [ [ ] [ ] ] " ; cout << swapCount ( s ) << " STRNEWLINE " ; return 0 ; }