Sub | 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
< ? php function nextIndex ( $ str , $ start , $ c ) { for ( $ i = $ start ; $ i < strlen ( $ str ) ; $ i ++ ) { if ( $ str [ $ i ] == $ c ) return $ i ; } return -1 ; } function countSubStrings ( $ str ) { $ n = strlen ( $ str ) ; $ countX = array ( 0 , $ n , NULL ) ; $ count = 0 ; for ( $ i = $ n - 1 ; $ i >= 0 ; $ i -- ) { if ( $ str [ $ i ] == ' x ' ) $ count ++ ; $ countX [ $ i ] = $ count ; } $ nextIndexX = nextIndex ( $ str , 0 , ' x ' ) ; $ 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 ; } $ s = " xyyxx " ; echo countSubStrings ( $ s ) ; ? >