Documentation Index
Fetch the complete documentation index at: /llms.txt
Use this file to discover all available pages before exploring further.
Tested Python solution for LeetCode 903 with 20 pytest cases. Generate a practice environment with lcpy.
lcpy gen -n 903 # by problem number
lcpy gen -s valid_permutations_for_di_sequence # by problem name
s of length n where s[i] is either:
'D' means decreasing, or'I' means increasing.perm of n + 1 integers of all the integers in the range [0, n] is called a valid permutation if for all valid i:
s[i] == 'D', then perm[i] > perm[i + 1], ands[i] == 'I', then perm[i] < perm[i + 1].perm. Since the answer may be large, return it modulo 10^9 + 7.
Input: s = "DID"
Output: 5
Input: s = "D"
Output: 1
n == s.length1 <= n <= 200s[i] is either 'I' or 'D'.class Solution:
# Time: O(n^2)
# Space: O(n)
def num_perms_di_sequence(self, s: str) -> int:
mod = 1_000_000_007
n = len(s)
# dp[j] = ways to place values so far where the last value is the
# j-th smallest of the values still unused.
dp = [1] * (n + 1)
for i, ch in enumerate(s):
m = n + 1 - i
ndp = [0] * (m - 1)
if ch == "I":
# next value is larger: its rank is at least the last rank
run = 0
for j in range(m - 1):
run = (run + dp[j]) % mod
ndp[j] = run
else:
# next value is smaller: its rank is strictly below the last rank
suf = 0
for j in range(m - 2, -1, -1):
suf = (suf + dp[j + 1]) % mod
ndp[j] = suf
dp = ndp
return dp[0]
| Time | Space |
|---|---|
| O(n^2) | O(n) |