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

What is Recursion? How it is work? understand in less than 5 minutes.

The Only Way To Make Money As A Programmer

Understanding Class and Objects

Kotlin and Rx2. How I wasted 5 hours because of wrong brackets

The Vale Workflow

Simplify S3 Event Notifications with Terraform and the S3 Event Bus

How to download .pkpass in flutter

How We Procedurally Generated Disney Melee Mania’s Vegetation

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

Color of Next Ball Puzzle

Solve Top LeetCode Problem Smartly

Interview Questions For Developers To Ask Potential Employers

1570. Dot Product of Two Sparse Vectors