Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Common Digit Longest Subsequence

Moderate
0/80
Average time to solve is 31m
17 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 )
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
Full screen
Console