903. Valid Permutations for DI Sequence
IntuitionApproachComplexity
Time complexity:

Space complexity:
Code
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->

# Approach
<!-- Describe your approach to solving the problem. -->

# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```cpp []
class Solution {
public:
    int numPermsDISequence(string s) {
        int n = s.size(), mod = 1e9 + 7;
        vector<int> dp(n + 1, 1), temp(n + 1);

        for (int i = 1; i <= n; ++i) {
            if (s[i - 1] == 'I') {
                for (int j = 0, sum = 0; j <= n - i; ++j) {
                    sum = (sum + dp[j]) % mod;
                    temp[j] = sum;
                }
            } else {
                for (int j = n - i, sum = 0; j >= 0; --j) {
                    sum = (sum + dp[j + 1]) % mod;
                    temp[j] = sum;
                }
            }
            swap(dp, temp);
        }

        return dp[0];
    }
};

```
['C++']