New update is available. Click here to update.

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