Valid Permutations for DI Sequence

Problem Description

You are given a string s of length n where s[i] is either:

• 'D' means decreasing, or
• 'I' means increasing.

A permutation perm of n + 1 integers of all the integers in the range [0, n] is called a valid permutation if for all valid i:

• If s[i] == 'D', then perm[i] > perm[i + 1], and
• If s[i] == 'I', then perm[i] < perm[i + 1].

Return the number of valid permutations perm. Since the answer may be large, return it modulo 10^9 + 7.

Key Insights

• The problem can be approached using dynamic programming.
• We can leverage the concept of counting permutations based on the conditions set by the characters in the string.
• The number of valid permutations can be computed by counting the ways to fill increasing and decreasing segments defined by the I and D characters.

Space and Time Complexity

Time Complexity: O(n^2)
Space Complexity: O(n)

Solution

The solution uses dynamic programming to maintain the count of valid permutations based on the current position in the string. We define a DP table where dp[i][j] represents the number of valid permutations of the first i numbers with j being the last number. The transitions depend on whether the previous character was I or D, allowing us to fill the table while maintaining the conditions for valid permutations.

Code Solutions