Common Digit Longest Subsequence

Posted: 4 Aug, 2020
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

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].
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
Approach 1

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.

Try Problem