Common Digit Longest Subsequence— Asked in Amazon Interview

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.

Sample Input:

7
11 122 77 92 55 69 98

Sample Output:

5

Approach :

Space Optimized DP

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.

Time Complexity — O(N)
Space Complexity — O(1)

Code :

Thanks for Reading

Placewit grows the best engineers by providing an interactive classroom experience and by helping them develop their skills and get placed in amazing companies.

Learn more at Placewit. Follow us on Instagram and Facebook for daily learning.