Count of sub | C ++ implementation of the approach ; Function to return the total required sub - sequences ; Find ways for all values of x ; x + 1 ; Removing all unnecessary digits ; Prefix Sum Array for X + 1 digit ; Sum of squares ; Previous sum of all possible pairs ; To find sum of multiplication of all possible pairs ; To prevent overcounting ; Adding ways for all possible x ; Driver code
#include <bits/stdc++.h> NEW_LINE #define ll  long long int NEW_LINE #define MOD  1000000007 NEW_LINE using namespace std ; int solve ( string test ) { int size = test . size ( ) ; int total = 0 ; for ( int i = 0 ; i <= 8 ; i ++ ) { int x = i ; int y = i + 1 ; string newtest ; for ( int j = 0 ; j < size ; j ++ ) { if ( test [ j ] == x + 48 test [ j ] == y + 48 ) { newtest += test [ j ] ; } } if ( newtest . size ( ) > 0 ) { int size1 = newtest . size ( ) ; int prefix [ size1 ] = { 0 } ; for ( int j = 0 ; j < size1 ; j ++ ) { if ( newtest [ j ] == y + 48 ) { prefix [ j ] ++ ; } } for ( int j = 1 ; j < size1 ; j ++ ) { prefix [ j ] += prefix [ j - 1 ] ; } int count = 0 ; int firstcount = 0 ; int ss = 0 ; int prev = 0 ; for ( int j = 0 ; j < size1 ; j ++ ) { if ( newtest [ j ] == x + 48 ) { count ++ ; firstcount ++ ; } else { ss += count * count ; int pairsum = ( firstcount * firstcount - ss ) / 2 ; int temp = pairsum ; pairsum -= prev ; prev = temp ; int secondway = prefix [ size1 - 1 ] ; if ( j != 0 ) secondway -= prefix [ j - 1 ] ; int answer = count * ( count - 1 ) * secondway * ( secondway - 1 ) ; answer /= 4 ; answer += ( pairsum * secondway * ( secondway - 1 ) ) / 2 ; total += answer ; count = 0 ; } } } } return total ; } int main ( ) { string test = "13134422" ; cout << solve ( test ) << endl ; return 0 ; }