C++ with comments. O(N) time O(1) space. Beats 100%.
The idea is to count the strings ending on a particular vowel. Here are how these counts go:\n\n\n    a       e       i        o      u\n\t1       1       1    
The idea is to count the strings ending on a particular vowel. Here are how these counts go:\n\n```\n    a       e       i        o      u\n\t1       1       1        1      1\n\t1       2       3        4      5\n\t1       3       6       10     15\n```\n\nYou get the idea: at each iteration there is a single string ending on \'a\', the one with \'a\' only. Starting with index 1, the number of strings ending with this letter is the sum off the previous line up to and including the index. We only need to keep the last row, and accumulate all the counts. This is constant space.\n\n```\nclass Solution {\npublic:\n    int countVowelStrings(int n) {\n        if(n == 0) return 0;\n        \n        // Number of strings of length 1 ending on: a, e, i, o, u\n        array<int, 5> counts = { 1, 1, 1, 1, 1 };\n        \n        for(int i = 1; i < n; ++i) {\n            // Only one string ending on \'a\' on each iteration. Start with 1.`\n            for(int j = 1; j < 5; ++j) {\n                counts[j] += counts[j-1];\n            }\n        }\n        \n        return accumulate(counts.begin(), counts.end(), 0);\n    }\n};\n```
[]