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 , prthe answer ; Driver Code
def countPossiblities ( arr , n ) : NEW_LINE INDENT lastOccur = [ - 1 ] * 100000 NEW_LINE dp = [ 0 ] * ( n + 1 ) NEW_LINE dp [ 0 ] = 1 NEW_LINE for i in range ( 1 , n + 1 ) : NEW_LINE INDENT curEle = arr [ i - 1 ] NEW_LINE dp [ i ] = dp [ i - 1 ] NEW_LINE if ( lastOccur [ curEle ] != - 1 and lastOccur [ curEle ] < i - 1 ) : NEW_LINE INDENT dp [ i ] += dp [ lastOccur [ curEle ] ] NEW_LINE DEDENT lastOccur [ curEle ] = i NEW_LINE DEDENT print ( dp [ n ] ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 1 , 2 , 1 , 2 , 2 ] NEW_LINE N = len ( arr ) NEW_LINE countPossiblities ( arr , N ) NEW_LINE DEDENT