Last Updated: 4 Aug, 2020

Common Digit Longest Subsequence

Moderate

Asked in companies

Solve now

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

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

Solve now

Approaches

01 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.

Initialize the maxLength result with 0.
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.

Solve now

02 Approach

We will write an iterative DP of size N*10 where dp[i][j] denotes the length of the longest subsequence till ‘i’ elements having the last element-containing ‘j’ as a digit.

Make a DP matrix dp[n+1][10] and initialize the ‘0’th row with 0 as the length of the longest subsequence till 0 elements are 0.
Now, iterate through i = 1 to i = n and for each i:
1. Initialize currentMax =0.
2. Maintain a bool array digitsOfCurrentNumber to mark the digits appeared in ‘i’th number and also keep maximizing the currentMax.
3. Let’s say digit ‘d’ appeared in ‘i’th number then we can add this element in previous sub-sequence ending with element containing ‘d’ as digit:

currentMax = max(currentMax, dp[i-1][d] + 1)

4.Update the DP Matrix, for j=0 to j=9:

1. If ‘j’th digit appead in ‘i’th element then we should update it with our calculated currentMax:

dp[i][j] = currentMax

2. Else:

dp[i][j] = dp[i-1][j]

3. Finally Initialize the maxLength = 0.

4. Iterate over i= 0 to i =9 maximizing maxLength:

maxLength = max(maxLenght, dp[n][i])

5. Return maxLength.

Solve now

03 Approach

We will write an iterative Dynamic Programming Approach with DP array of size 10 where dp[i] denotes the length of longest subsequence having the last element containing ‘i’ as a digit.

Make a DP array dp[10] and initialize with 0 as initially, the length of the longest subsequence is 0.
Initialize the maxLength with 0.
Now, iterate through i = 0 to i = n-1 and for each i:
1. Initialize currentMax =0.
2. Maintain a bool array digitsOfCurrentNumber to mark the digits appeared in ‘i’th number and also keep maximizing the currentMax.
3. Let’s say digit ‘d’ appeared in ‘i’th number then we can add this element in previous sub-sequence ending with element containing ‘d’ as digit:

currentMax = max(currentMax, dp[d] + 1

4. Update the DP array, for j=0 to j=9:

1. If ‘j’th digit appead in ‘i’th element then we should update it with our calculated currentMax:

dp[j] = currentMax

5. Update the maxLength:

maxLength = max(maxLength, currentMax)

4. Return the maxLength.

Solve now