LeetCode 1955: Count Number of Special Subsequences Solution

Master LeetCode problem 1955 (Count Number of Special Subsequences), 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.

1955. Count Number of Special Subsequences

Hard

Array Dynamic Programming

Problem Explanation

Explanation

To solve this problem, we can use dynamic programming. We will iterate through the given array nums and maintain three counts: dp0 for the number of special subsequences ending with 0, dp1 for the number of special subsequences ending with 1, and dp2 for the number of special subsequences ending with 2. We update these counts based on the current element being processed.

When processing 0, we update dp0 = dp0 * 2 + 1, dp1 and dp2 remain the same.
When processing 1, we update dp1 = dp1 * 2 + dp0, dp0 remains the same, and dp2 remains the same.
When processing 2, we update dp2 = dp2 * 2 + dp1, dp0 and dp1 remain the same.

Finally, the total number of special subsequences is given by dp2.

Time Complexity: O(n) Space Complexity: O(1)

Solution Code

class Solution {
    public int countSpecialSubsequences(int[] nums) {
        final int MOD = 1000000007;
        int dp0 = 0, dp1 = 0, dp2 = 0;
        
        for (int num : nums) {
            if (num == 0) {
                dp0 = (dp0 * 2 % MOD + 1) % MOD;
            } else if (num == 1) {
                dp1 = (dp1 * 2 % MOD + dp0) % MOD;
            } else {
                dp2 = (dp2 * 2 % MOD + dp1) % MOD;
            }
        }
        
        return dp2;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1955 (Count Number of Special Subsequences)?

This page provides optimized solutions for LeetCode problem 1955 (Count Number of Special Subsequences) 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 1955 (Count Number of Special Subsequences)?

The time complexity for LeetCode 1955 (Count Number of Special Subsequences) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1955 on DevExCode?

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

Back to LeetCode Solutions