Count of lexicographically smaller characters on right | Function to count the smaller characters on the right of index i ; store the length of string ; initialize each elements of arr to zero ; array to store count of smaller characters on the right side of that index ; initialize the variable to store the count of characters smaller than that at index i ; adding the count of characters smaller than index i ; print the count of characters smaller than index i stored in ans array ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; void countSmaller ( string str ) { int n = str . length ( ) ; int arr [ 26 ] = { 0 } ; int ans [ n ] ; for ( int i = n - 1 ; i >= 0 ; i -- ) { arr [ str [ i ] - ' a ' ] ++ ; int ct = 0 ; for ( int j = 0 ; j < str [ i ] - ' a ' ; j ++ ) { ct += arr [ j ] ; } ans [ i ] = ct ; } for ( int i = 0 ; i < n ; i ++ ) { cout << ans [ i ] << " ▁ " ; } } int main ( ) { string str = " edcbaa " ; countSmaller ( str ) ; return 0 ; }