Count subsequence of length three in a given string | Function to find number of occurrences of a subsequence of length three in a string ; calculate length of string ; auxiliary array to store occurrences of first character ; auxiliary array to store occurrences of third character ; calculate occurrences of first character upto ith index from left ; calculate occurrences of third character upto ith index from right ; variable to store total number of occurrences ; loop to find the occurrences of middle element ; if middle character of subsequence is found in the string ; multiply the total occurrences of first character before middle character with the total occurrences of third character after middle character ; Driver Code
< ? php function findOccurrences ( $ str , $ substr ) { $ n = strlen ( $ str ) ; $ preLeft = array ( 0 ) ; $ preRight = array ( 0 ) ; if ( $ str [ 0 ] == $ substr [ 0 ] ) $ preLeft [ 0 ] ++ ; for ( $ i = 1 ; $ i < $ n ; $ i ++ ) { if ( $ str [ $ i ] == $ substr [ 0 ] ) $ preLeft [ $ i ] = $ preLeft [ $ i - 1 ] + 1 ; else $ preLeft [ $ i ] = $ preLeft [ $ i - 1 ] ; } if ( $ str [ $ n - 1 ] == $ substr [ 2 ] ) $ preRight [ $ n - 1 ] ++ ; for ( $ i = $ n - 2 ; $ i >= 0 ; $ i -- ) { if ( $ str [ $ i ] == $ substr [ 2 ] ) $ preRight [ $ i ] = ( $ preRight [ $ i + 1 ] + 1 ) ; else $ preRight [ $ i ] = $ preRight [ $ i + 1 ] ; } $ counter = 0 ; for ( $ i = 1 ; $ i < $ n - 1 ; $ i ++ ) { if ( $ str [ $ i ] == $ str [ 1 ] ) { $ total = $ preLeft [ $ i - 1 ] * $ preRight [ $ i + 1 ] ; $ counter += $ total ; } } return $ counter ; } $ str = " GFGFGYSYIOIWIN " ; $ substr = " GFG " ; echo findOccurrences ( $ str , $ substr ) ; ? >