We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Valid Permutations for DI Sequence

Number: 939

Difficulty: Hard

Paid? No

Companies: N/A

Problem Description

Given a string s consisting of characters 'I' and 'D' of length n, count the number of valid permutations of [0, n] such that for each index i, if s[i] == 'I', then perm[i] < perm[i + 1] and if s[i] == 'D', then perm[i] > perm[i + 1]. Return the count modulo 10^9 + 7.

Key Insights

  • Use dynamic programming to build up the solution.
  • Define dp[i][j] where i represents the length of the permutation constructed (or the number of characters processed) and j represents the ending “rank” or value position among the remaining choices.
  • For an 'I', valid transitions come from summing dp[i-1][0] to dp[i-1][j-1]. For a 'D', they come from summing dp[i-1][j] to dp[i-1][i-1].
  • Optimize summing operations using prefix sum arrays to reduce time complexity.

Space and Time Complexity

Time Complexity: O(n^2) – We compute DP transitions in quadratic time using prefix sums. Space Complexity: O(n^2) – The dp table requires O((n+1)*(n+1)) space.

Solution

We solve the problem using a 2D dynamic programming approach. Let dp[i][j] be the number of ways to arrange i+1 numbers (forming a valid permutation up to that point) such that the last placed number is in the j-th smallest order among the remaining unused numbers. The recurrence changes based on whether the current character in s is 'I' (increasing) or 'D' (decreasing).

For each position i (from 1 to n), based on the character s[i-1]:

  • If s[i-1] == 'I': We can only place a number that is larger than the previous one. This means the new rank must be chosen from the left side (all indices < j). Hence, dp[i][j] is the sum of dp[i-1][0] through dp[i-1][j-1].
  • If s[i-1] == 'D': We require a number smaller than the previous, so dp[i][j] is the sum of dp[i-1][j] through dp[i-1][i-1], i.e., the count for all ranks from j upward.

To quickly compute these summations, we maintain cumulative prefix sums at each DP step. Finally, the answer is the sum of dp[n][j] for all j from 0 to n. All summations use modulo arithmetic (mod = 10^9 + 7) due to the possible large numbers.

Code Solutions

MOD = 10**9 + 7

def numPermsDISequence(s: str) -> int:
    n = len(s)
    # dp[i][j]: number of ways to form valid permutation of length i+1 with ending rank j
    dp = [[0] * (n + 1) for _ in range(n + 1)]
    dp[0][0] = 1  # base case: only one permutation of one element
    
    for i in range(1, n + 1):
        # prefix sum for i-1 row for fast range sum queries
        prefix = [0] * (n + 2)
        for j in range(i):
            prefix[j+1] = (prefix[j] + dp[i-1][j]) % MOD
        
        if s[i-1] == 'I':
            # For 'I', the current number must be greater than the previous,
            # so choose ending rank j using sum of dp[i-1][0...j-1]
            for j in range(i + 1):
                dp[i][j] = prefix[j] % MOD
        else:  # s[i-1] == 'D'
            # For 'D', the current number must be less than the previous,
            # so choose ending rank j using sum of dp[i-1][j...i-1]
            for j in range(i + 1):
                dp[i][j] = (prefix[i] - prefix[j]) % MOD
    # Sum all possibilities from dp[n][*]
    return sum(dp[n]) % MOD

# Example usage:
if __name__ == "__main__":
    print(numPermsDISequence("DID"))  # Expected output: 5
← Back to All Questions