# 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)