FastPrep
Problem · Dynamic Programming

Colorful Increasing Subsequences

Learn this problem
● HardAtlassian logoAtlassianINTERNFULLTIMEOA

Problem statement

Each candle has a height and one of k colors. Count subsequences whose heights are strictly increasing and that contain every color at least once. Return the result modulo 10^9 + 7.

Function

countColorfulSubsequences(heights: int[], colors: int[], k: int) → int

Examples

Example 1

heights = [1,3,2,4]colors = [1,2,2,3]k = 3return = 2

The two valid subsequences choose height 1, either height 2 or 3, and height 4.

Constraints

  • 2 <= heights.length = colors.length <= 100
  • 1 <= k <= 7
  • 1 <= colors[i] <= k
  • 1 <= heights[i] <= 10^9

More Atlassian problems

drafts saved locally
public int countColorfulSubsequences(int[] heights, int[] colors, int k) {
  // Write your code here.
}
heights[1,3,2,4]
colors[1,2,2,3]
k3
expected2
checking account