Count of sub | Java Implementation of above 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
import java . io . * ; class GFG { static int solve ( String test , int MOD ) { int size = test . length ( ) ; 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 . charAt ( j ) == x + 48 || test . charAt ( j ) == y + 48 ) { newtest += test . charAt ( j ) ; } } if ( newtest . length ( ) > 0 ) { int size1 = newtest . length ( ) ; int [ ] prefix = new int [ size1 ] ; for ( int j = 0 ; j < size1 ; j ++ ) { prefix [ j ] = 0 ; if ( newtest . charAt ( 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 . charAt ( 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 ; } public static void main ( String [ ] args ) { String test = "13134422" ; int MOD = 1000000007 ; System . out . println ( solve ( test , MOD ) ) ; } }