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 function
function findOccurrences ( str , substr ) { let n = str . length ; let preLeft = new Array ( n ) ; preLeft . fill ( 0 ) ; let preRight = new Array ( n ) ; preRight . fill ( 0 ) ; if ( str [ 0 ] == substr [ 0 ] ) preLeft [ 0 ] ++ ; for ( let 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 ( let i = n - 2 ; i >= 0 ; i -- ) { if ( str [ i ] == substr [ 2 ] ) preRight [ i ] = preRight [ i + 1 ] + 1 ; else preRight [ i ] = preRight [ i + 1 ] ; } let counter = 0 ; for ( let i = 1 ; i < n - 1 ; i ++ ) { if ( str [ i ] == str [ 1 ] ) { let total = preLeft [ i - 1 ] * preRight [ i + 1 ] ; counter += total ; } } return counter ; } let str = " " ; let substr = " " ; document . write ( findOccurrences ( str , substr ) ) ;