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.
11 122 77 92 55 69 98
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)