Sub | C ++ implementation of the approach ; Function that returns the index of next occurrence of the character c in string str starting from index start ; Starting from start ; If current character = c ; Not found ; Function to return the count of required sub - strings ; Stores running count of ' x ' starting from the end ; Next index of ' x ' starting from index 0 ; Next index of ' y ' starting from index 0 ; To store the count of required sub - strings ; If ' y ' appears before ' x ' it won 't contribute to a valid sub-string ; Find next occurrence of ' y ' ; If ' y ' appears after ' x ' every sub - string ending at an ' x ' appearing after this ' y ' and starting with the current ' x ' is a valid sub - string ; Find next occurrence of ' x ' ; Return the count ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int nextIndex ( string str , int start , char c ) { for ( int i = start ; i < str . length ( ) ; i ++ ) { if ( str [ i ] == c ) return i ; } return -1 ; } int countSubStrings ( string str ) { int i , n = str . length ( ) ; int countX [ n ] ; int count = 0 ; for ( i = n - 1 ; i >= 0 ; i -- ) { if ( str [ i ] == ' x ' ) count ++ ; countX [ i ] = count ; } int nextIndexX = nextIndex ( str , 0 , ' x ' ) ; int nextIndexY = nextIndex ( str , 0 , ' y ' ) ; count = 0 ; while ( nextIndexX != -1 && nextIndexY != -1 ) { if ( nextIndexX > nextIndexY ) { nextIndexY = nextIndex ( str , nextIndexY + 1 , ' y ' ) ; continue ; } else { count += countX [ nextIndexY ] ; nextIndexX = nextIndex ( str , nextIndexX + 1 , ' x ' ) ; } } return count ; } int main ( ) { string s = " xyyxx " ; cout << countSubStrings ( s ) ; }