Count distinct sequences obtained by replacing all elements of subarrays having equal first and last elements with the first element any number of times | Function to count number of sequences satisfying the given criteria ; Stores the index of the last occurrence of the element ; Initialize an array to store the number of different sequences that are possible of length i ; Base Case ; If no operation is applied on ith element ; If operation is applied on ith element ; Update the last occurrence of curEle ; Finally , prlet the answer ; Driver Code
function countPossiblities ( arr , n ) { let lastOccur = new Array ( 100000 ) ; for ( let i = 0 ; i < n ; i ++ ) { lastOccur [ i ] = - 1 ; } dp = new Array ( n + 1 ) ; dp [ 0 ] = 1 ; for ( let i = 1 ; i <= n ; i ++ ) { let curEle = arr [ i - 1 ] ; dp [ i ] = dp [ i - 1 ] ; if ( lastOccur [ curEle ] != - 1 & lastOccur [ curEle ] < i - 1 ) { dp [ i ] += dp [ lastOccur [ curEle ] ] ; } lastOccur [ curEle ] = i ; } document . write ( dp [ n ] + " " ) ; } let arr = [ 1 , 2 , 1 , 2 , 2 ] ; let N = arr . length ; countPossiblities ( arr , N ) ;