Common Digit Longest Subsequence

Moderate
0/80
Average time to solve is 31m
18 upvotes
Asked in companies
AmazonSamsungOptum

Problem statement

You have been given an array of 'N' Integers. Find the length of the longest subsequence such that each adjacent element of the subsequence has at least one digit in common.

Note : 
A sequence 'A' is a subsequence of a sequence 'B' if 'A' can be obtained from 'B' by deletion of several (possibly, zero) elements. For example, [3,1] is a subsequence of [3,2,1] and [4,3,1], but not a subsequence of [1,3,3,7] and [3,10,4].
Detailed explanation ( Input/output format, Notes, Images )
Input format : 
The first line of each test case contains an Integer 'N' denoting the size of the array.

The second line of each test case contains 'N' space-separated integers denoting the elements of the array.
Output format : 
Print the length of the longest subsequence such that each adjacent elements of the subsequence have at least one digit in common.
Note: 
You are not required to print the output explicitly, it has already been taken care of. Just implement the function.
Constraints : 
1 <= N <= 10 ^ 5
1 <= Arr[i] <= 10 ^ 9

Where Arr[i] is the i-th element in the array.

Time Limit: 1sec
Sample Input 1 :
7
11 122 77 92 55 69 98
Sample Output 1 :
5
 Explanation to Sample Input 1 :
The longest subsequence is: 11 122 92 69 98
Sample Input 2 :
6
21 32 65 34 83 95
Sample Output 2 :
4
 Explanation to Sample Input 2 :
The longest subsequence is: 21 32 34 83
Hint

Can you relate this problem to Dynamic Programming Problem of Longest Increasing Subsequence and think of a similar solution.

Approaches (3)
DP Approach

We will write an iterative DP similar to LIS where dp[i] denotes the length of the longest subsequence ending at ‘i’th element.

  1. Initialize the maxLength result with 0.
  2. Now, iterate through i = 0 to i = n-1 and for each i:
    1. Initialize dp[i] = 1 as we can have a subsequence of 1 length with this element.
    2. Maintain a bool array digitsOfCurrentNumber to mark the digits appeared in ‘i’th number.
    3. Iterate through j=0 to j<i and for each j: check for common digit
    4. If there is a common digit then update:

                  dp[i] = max(dp[i], dp[j] + 1)

         5. Update the maxLength with:

                  maxLength = max(maxLength, dp[i])

    3. Return the maxLength.

Time Complexity

O(N ^ 2), where ‘N’ is the size of the array.

 

We are using the Dynamic Programming Approach and we are looping over j=0 to j<i for all the values of i=0 to i=n-1. The number of iterations is (N*(N+1))/2 and it takes constant time to iterate through the digits of the numbers, so the Overall Time Complexity is O(N ^ 2).

Space Complexity

O(N), where ‘N’ is the size of the array.

 

We are using DP Matrix of size N. Hence, the overall Space Complexity is O(N).

Code Solution
(100% EXP penalty)
Common Digit Longest Subsequence
Full screen
Console