1220. Count Vowels Permutation

 一刷 08/2022

Version #1 1D DP

Time O(N)

Space O(1)

Runtime: 9 ms, faster than 98.38% of Java online submissions for Count Vowels Permutation.

Memory Usage: 41.6 MB, less than 68.76% of Java online submissions for Count Vowels Permutation.

class Solution {

    private int MOD = (int)(1e9 + 7);

    public int countVowelPermutation(int n) {

        //0 a -> e

        //1 e -> a, i

        //2 i -> a, e, o, u

        //3 o -> i, u

        //4 u -> a

        // number of combinations with length i and ending with char (a,e,i,o,u)

        int[] dp = new int[5];

        Arrays.fill(dp, 1);

        for (int i = 2; i <= n; i++) {

            int[] ndp = new int[5];

            // a can follow e,i,u

            ndp[0] = ((dp[1] + dp[2]) % MOD + dp[4]) % MOD;

            // e can follow a,i

            ndp[1] = (dp[0] + dp[2]) % MOD;

            // i can follow e,o

            ndp[2] = (dp[1] + dp[3]) % MOD;

            // o can follow i

            ndp[3] = dp[2];

            // u can follow i,o

            ndp[4] = (dp[2] + dp[3]) % MOD;

            dp = ndp;

        }

        int sum = 0;

        for (int i = 0; i < 5; i++) {

            sum = (sum + dp[i]) % MOD;

        }

        return sum;

    }

}