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.

--

--

--

Upskilling students for tech placements!

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Performance Test With Selenium

The One Guide To Set Up A Rails Application

SQL(Fetch Many and Fetch One):

Deconstructing the NSF CAREER Proposal

How to Set up a VPN Server Using SoftEther

Extend Your Business with a Hybrid Cloud Solution

iOS 11 & Swift 4 Udemy tutorial (notes)

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Placewit

Placewit

Upskilling students for tech placements!

More from Medium

LeetCode 146. LRU Cache

Longest Increasing Subsequence Coding Question

PlatinumX Tech’s Algorithm Expert Course Review (How I got into Turing).

“Delete and Earn” problem using Dynamic Programming