Print all positions of a given string having count of smaller characters equal on both sides | C ++ program to implement the above approach ; Function to find indexes of the given string that satisfy the condition ; Stores length of given string ; Stores frequency of each character of str ; Update frequency of current character ; cntLeftFreq [ i ] Stores frequency of characters present on the left side of index i . ; Traverse the given string ; Stores count of smaller characters on left side of i . ; Stores count of smaller characters on Right side of i . ; Traverse smaller characters on left side of index i . ; Update cntLeft ; Update cntRight ; Update cntLeftFreq [ str [ i ] ] ; If count of smaller elements on both sides equal ; Print current index ; ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; void printIndexes ( string str ) { int N = str . length ( ) ; int cntFreq [ 256 ] = { 0 } ; for ( int i = 0 ; i < N ; i ++ ) { cntFreq [ str [ i ] ] ++ ; } int cntLeftFreq [ 256 ] = { 0 } ; for ( int i = 0 ; i < N ; i ++ ) { int cntLeft = 0 ; int cntRight = 0 ; for ( int j = str [ i ] - 1 ; j >= 0 ; j -- ) { cntLeft += cntLeftFreq [ j ] ; cntRight += cntFreq [ j ] - cntLeftFreq [ j ] ; } cntLeftFreq [ str [ i ] ] ++ ; if ( cntLeft == cntRight && cntLeft != 0 ) { cout << i << " ▁ " ; } } } int main ( ) { string str = " aabacdabbb " ; printIndexes ( str ) ; }