LeetCode 903: Valid Permutations for DI Sequence Solution

Master LeetCode problem 903 (Valid Permutations for DI Sequence), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

903. Valid Permutations for DI Sequence

Hard

String Dynamic Programming Prefix Sum

Problem Explanation

Explanation:

To solve this problem, we can use dynamic programming. We will define a 2D array dp where dp[i][j] represents the number of valid permutations of length i ending with the number j.

Initialize dp as a 2D array of size (n+1) x (n+1) with all values set to 0.
Base case: dp[1][0] = 1.
For each position i from 2 to n+1 and each number j from 0 to i:
- If s[i-2] == 'D', then dp[i][j] = sum(dp[i-1][k]) for all k from j to i-1.
- If s[i-2] == 'I', then dp[i][j] = sum(dp[i-1][k]) for all k from 0 to j-1.
Finally, the answer is the sum of all elements in the last row of dp modulo 10^9 + 7.

Solution Code

class Solution {
    public int numPermsDISequence(String s) {
        int n = s.length();
        int MOD = 1000000007;
        int[][] dp = new int[n + 1][n + 1];
        dp[0][0] = 1;

        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= i; j++) {
                if (s.charAt(i - 1) == 'D') {
                    for (int k = j; k < i; k++) {
                        dp[i][j] = (dp[i][j] + dp[i - 1][k]) % MOD;
                    }
                } else {
                    for (int k = 0; k < j; k++) {
                        dp[i][j] = (dp[i][j] + dp[i - 1][k]) % MOD;
                    }
                }
            }
        }

        int result = 0;
        for (int num : dp[n]) {
            result = (result + num) % MOD;
        }

        return result;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 903 (Valid Permutations for DI Sequence)?

This page provides optimized solutions for LeetCode problem 903 (Valid Permutations for DI Sequence) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 903 (Valid Permutations for DI Sequence)?

The time complexity for LeetCode 903 (Valid Permutations for DI Sequence) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 903 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 903 in Java, C++, or Python.

Back to LeetCode Solutions