6

Common Digit Longest Subsequence

Difficulty: MEDIUM
Avg. time to solve
31 min

Problem Statement
Suggest Edit

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
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
Reset Code
Full screen
copy-code
Console