#2963
Count the Number of Good Partitions
candidate master · 1450 · lc hard +32 · verified · 49.1% accepted · 308 likes · top 35%
Description
Given a 0-indexed array nums of positive integers, a partition into contiguous subarrays is good when every distinct value is confined to exactly one subarray.
Count all good partitions of nums and return the result modulo 109 + 7.
Example 1:
Input: nums = [1,2,3,4]
Output: 8
Explanation: The 8 possible good partitions are: ([1], [2], [3], [4]), ([1], [2], [3,4]), ([1], [2,3], [4]), ([1], [2,3,4]), ([1,2], [3], [4]), ([1,2], [3,4]), ([1,2,3], [4]), and ([1,2,3,4]).
Example 2:
Input: nums = [1,1,1,1]
Output: 1
Explanation: The only possible good partition is: ([1,1,1,1]).
Example 3:
Input: nums = [1,2,1,3]
Output: 2
Explanation: The 2 possible good partitions are: ([1,2,1], [3]) and ([1,2,1,3]).
Code
1
2
3