Longest subsequence such that adjacent elements have at least one common digit

Given an array arr[] of N integers, the task is to find the length of the longest sub-sequence such that adjacent elements of the sub-sequence have at least one digit in common.
Examples: 
 

Input: arr[] = {1, 12, 44, 29, 33, 96, 89} 
Output: 5 
The longest sub-sequence is {1 12 29 96 89}
Input: arr[] = {12, 23, 45, 43, 36, 97} 
Output: 4 
The longest sub-sequence is {12 23 43 36} 
 

Approach: The idea is to store the length of longest sub-sequence for each digit present in an element of the array. 
 

• dp[i][d] represents the length of the longest sub-sequence up to ith element if digit d is the common digit.

• Declare a cnt array and set cnt[d] = 1 for each digit present in current element.

• Consider each digit d as common digit and find maximum length sub-sequence ending at arr[i] as dp[i][d] = max(dp[j][d]+1) (0<=j<i).

• Also find a local maximum max(dp[i][d]) for current element.

• After finding local maximum update dp[i][d] for all digits present in the current element to a local maximum.

• This is required as local maximum represents maximum length sub-sequence for an element having digit d.

E.g. Consider arr[] = {24, 49, 96}. 
The local maximum for 49 is 2 obtain from digit 4. 
This local maximum will be used in finding the local maximum for 96 with common digit 9. 
For that it is required for all digits in 49, dp[i][d] should be set to local maximum.

Below is the implementation of the above approach: 

5

Time Complexity: O(n²) 
Auxiliary Space: O(n)
The auxiliary space required for above solution can be further reduced. Observe that for each digit d present in arr[i], it is required to find maximum length sub-sequence upto that digit irrespective of the fact that at which element the sub-sequence end. This reduces auxiliary space required to O(1). For each arr[i], find local maximum and update dig[d] for each digit d in arr[i] to local maximum. 
Below is the implementation of the above approach: 
 

5

Time Complexity: O(n) 
Auxiliary Space: O(1)
 

Using Brute Force:

Approach:

We can generate all possible sub-sequences of the given sequence and check if any adjacent elements have at least one common digit 3. We can then return the length of the longest sub-sequence that satisfies this condition.

Define a function has_common_digit(a, b) that takes two integers a and b as input and returns True if they have at least one digit in common, otherwise False.

Define a function longest_subsequence(arr) that takes a list of integers arr as input and returns the length of the longest subsequence of arr such that adjacent elements have at least one common digit.

Initialize a variable max_len to 0, which will store the length of the longest subsequence found so far.

Generate all possible subsequences of arr using a binary representation of integers from 0 to 2^n – 1, where n is the length of arr. Each bit in the binary representation represents the presence or absence of the corresponding element in the subsequence.

Check each subsequence generated in step 4 for validity: iterate over the subsequence and check if adjacent elements have at least one common digit using the has_common_digit function. If any adjacent elements do not have a common digit, mark the subsequence as invalid and move on to the next one.

If a valid subsequence is found, compare its length to max_len and update max_len if the length of the new subsequence is longer.

Return max_len as the length of the longest subsequence.

(Optional) Generate the longest subsequence itself by constructing a new list from the elements of arr that correspond to the 1-bits in the binary representation of the longest subsequence.

Input: arr1 = [1, 12, 44, 29, 33, 96, 89]
Output: 5
The longest sub-sequence is [1, 12, 29, 96, 89]
Input: arr2 = [12, 23, 45, 43, 36, 97]
Output: 4
The longest sub-sequence is [12, 23, 43, 36]

Time Complexity: O(2^n) where n is the length of the sequence
Space Complexity: O(n)