Count of subsequences of length 4 in form ( x , x , x + 1 , x + 1 ) | Set 2 | C ++ program for the above approach ; Function to count the numbers ; Array that stores the digits from left to right ; Array that stores the digits from right to left ; Initially both array store zero ; Fill the table for count1 array ; Update the count of current character ; Fill the table for count2 array ; Update the count of cuuent character ; Variable that stores the count of the numbers ; Traverse Input string and get the count of digits from count1 and count2 array such that difference b / w digit is 1 & store it int c1 & c2 . And store it in variable c1 and c2 ; Update the ans ; Return the final count ; Driver Code ; Given String ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; int countStableNum ( string str , int N ) { int count1 [ N ] [ 10 ] ; int count2 [ N ] [ 10 ] ; for ( int i = 0 ; i < N ; i ++ ) for ( int j = 0 ; j < 10 ; j ++ ) count1 [ i ] [ j ] = count2 [ i ] [ j ] = 0 ; for ( int i = 0 ; i < N ; i ++ ) { if ( i != 0 ) { for ( int j = 0 ; j < 10 ; j ++ ) { count1 [ i ] [ j ] += count1 [ i - 1 ] [ j ] ; } } count1 [ i ] [ str [ i ] - '0' ] ++ ; } for ( int i = N - 1 ; i >= 0 ; i -- ) { if ( i != N - 1 ) { for ( int j = 0 ; j < 10 ; j ++ ) { count2 [ i ] [ j ] += count2 [ i + 1 ] [ j ] ; } } count2 [ i ] [ str [ i ] - '0' ] ++ ; } int ans = 0 ; for ( int i = 1 ; i < N - 1 ; i ++ ) { if ( str [ i ] == '9' ) continue ; int c1 = count1 [ i - 1 ] [ str [ i ] - '0' ] ; int c2 = count2 [ i + 1 ] [ str [ i ] - '0' + 1 ] ; if ( c2 == 0 ) continue ; ans = ( ans + ( c1 * ( ( c2 * ( c2 - 1 ) / 2 ) ) ) ) ; } return ans ; } int main ( ) { string str = "224353" ; int N = str . length ( ) ; cout << countStableNum ( str , N ) ; return 0 ; }