Longest subsequence such that adjacent elements have at least one common digit | Java program to find maximum length subsequence such that adjacent elements have at least one common digit ; Returns length of maximum length subsequence ; To store the length of the maximum length subsequence ; To store current element arr [ i ] ; To store the length of the sub - sequence ending at index i and having common digit d ; To store digits present in current element ; To store length of maximum length subsequence ending at index i ; For first element maximum length is 1 for each digit ; Find digits of each element , then find length of subsequence for each digit and then find local maximum ; Find digits in current element ; For each digit present find length of subsequence and find local maximum ; Update value of dp [ i ] [ d ] for each digit present in current element to local maximum found . ; Update maximum length with local maximum ; Driver code
class GFG { static int findSubsequence ( int arr [ ] , int n ) { int len = 1 ; int tmp ; int i , j , d ; int [ ] [ ] dp = new int [ n ] [ 10 ] ; int [ ] cnt = new int [ 10 ] ; int locMax ; tmp = arr [ 0 ] ; while ( tmp > 0 ) { dp [ 0 ] [ tmp % 10 ] = 1 ; tmp /= 10 ; } for ( i = 1 ; i < n ; i ++ ) { tmp = arr [ i ] ; locMax = 1 ; for ( int x = 0 ; x < 10 ; x ++ ) cnt [ x ] = 0 ; while ( tmp > 0 ) { cnt [ tmp % 10 ] = 1 ; tmp /= 10 ; } for ( d = 0 ; d <= 9 ; d ++ ) { if ( cnt [ d ] > 0 ) { dp [ i ] [ d ] = 1 ; for ( j = 0 ; j < i ; j ++ ) { dp [ i ] [ d ] = Math . max ( dp [ i ] [ d ] , dp [ j ] [ d ] + 1 ) ; locMax = Math . max ( dp [ i ] [ d ] , locMax ) ; } } } for ( d = 0 ; d <= 9 ; d ++ ) { if ( cnt [ d ] > 0 ) { dp [ i ] [ d ] = locMax ; } } len = Math . max ( len , locMax ) ; } return len ; } public static void main ( String [ ] args ) { int arr [ ] = { 1 , 12 , 44 , 29 , 33 , 96 , 89 } ; int n = arr . length ; System . out . println ( findSubsequence ( arr , n ) ) ; } }