Longest 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
def findSubsequence ( arr , n ) : NEW_LINE INDENT Len = 1 NEW_LINE tmp = 0 NEW_LINE i , j , d = 0 , 0 , 0 NEW_LINE dp = [ [ 0 for i in range ( 10 ) ] for i in range ( n ) ] NEW_LINE cnt = [ 0 for i in range ( 10 ) ] NEW_LINE locMax = 0 NEW_LINE tmp = arr [ 0 ] NEW_LINE while ( tmp > 0 ) : NEW_LINE INDENT dp [ 0 ] [ tmp % 10 ] = 1 NEW_LINE tmp //= 10 NEW_LINE DEDENT for i in range ( 1 , n ) : NEW_LINE INDENT tmp = arr [ i ] NEW_LINE locMax = 1 NEW_LINE cnt = [ 0 for i in range ( 10 ) ] NEW_LINE while ( tmp > 0 ) : NEW_LINE INDENT cnt [ tmp % 10 ] = 1 NEW_LINE tmp //= 10 NEW_LINE DEDENT for d in range ( 10 ) : NEW_LINE INDENT if ( cnt [ d ] ) : NEW_LINE INDENT dp [ i ] [ d ] = 1 NEW_LINE for j in range ( i ) : NEW_LINE INDENT dp [ i ] [ d ] = max ( dp [ i ] [ d ] , dp [ j ] [ d ] + 1 ) NEW_LINE locMax = max ( dp [ i ] [ d ] , locMax ) NEW_LINE DEDENT DEDENT DEDENT for d in range ( 10 ) : NEW_LINE INDENT if ( cnt [ d ] ) : NEW_LINE INDENT dp [ i ] [ d ] = locMax NEW_LINE DEDENT DEDENT Len = max ( Len , locMax ) NEW_LINE DEDENT return Len NEW_LINE DEDENT arr = [ 1 , 12 , 44 , 29 , 33 , 96 , 89 ] NEW_LINE n = len ( arr ) NEW_LINE print ( findSubsequence ( arr , n ) ) NEW_LINE