Java O(N) Solution with 1-D dp
\nclass Solution {\n    private boolean isVowelChar(char c) {\n        return c==\'a\' || c==\'e\' || c==\'i\' || c==\'o\' || c==\'u\';\n    }\n    public long 
```\nclass Solution {\n    private boolean isVowelChar(char c) {\n        return c==\'a\' || c==\'e\' || c==\'i\' || c==\'o\' || c==\'u\';\n    }\n    public long countVowels(String word) {\n        if (word == null || word.length() == 0) {\n            return 0L;\n        }\n        // create 1 dp array\n        long[] countVowelsToIndex = new long[word.length()]; \n        // this indicates total number of vowels of all substrings that end at index i\n        // set initial value\n        countVowelsToIndex[0] = isVowelChar(word.charAt(0)) ? 1 : 0;\n        // now fill in the dp\n        long res = 0L;\n        res += countVowelsToIndex[0];\n        for (int i=1; i < word.length(); i++) {\n            // check if current character is vowel\n            long cnt=0L;\n            if (isVowelChar(word.charAt(i))) {\n                // case 1: the current char is a vowel\n                // first add result from last index\n                cnt += countVowelsToIndex[i-1]; \n                // then add total number of chars count from [0,i], that is i+1\n                cnt += (i+1);\n            } else {\n                // case 2 : not a vowel\n                // just add result from last index\n                cnt += countVowelsToIndex[i-1];\n            }\n            countVowelsToIndex[i] = cnt;\n            res += countVowelsToIndex[i];\n        } // time=O(N), space=O(N)\n        return res;\n    }\n}\n```
[]