Very Easy Solution | No DP | No Math Formula | Solving for n = 3 reveals the pattern
\nThe problem seems like it will have a typical recursive solution,\nbut in reality it has a very trivial solution.\n\nImportant part of this problem is to rego
\nThe problem seems like it will have a typical recursive solution,\nbut in reality it has a very trivial solution.\n\nImportant part of this problem is to regonize the pattern.\n\nFor `n = 3`, let\'s see how many strings can be formed.\n\nIf start of the string is "aa", the third letter can be any of\n`{a, e, i, o, u}` and the string will still be lexicographically\nsorted. So there will be 5 strings. in total.\nSo, say` "aa" -> 5`.\nIf the start is "ae", the third letter can be `{e, i, o, u}`. \nNote that `a` can\'t be the third letter, otherwise the string \nwill not be lexicographically sorted. So count of strings will\nbe 4.\nSo, say` "ae" -> 4.`\nSimilarly, for `"ai" -> {i, o, u} -> 3`.\n```\n"ao" -> {o, u} -> 2.\n"au" -> {u} -> 1.\n```\n\nNow say start of the string is "ee".\n```\n"ee" -> {e, i, o, u} -> 4.\n"ei" -> {i, o, u} -> 3.\n"eo" -> {o, u} -> 2.\n"eu" -> {u} -> 1.\n```\n\nSimilarly,\n```\n"ii" -> {i, o, u} -> 3.\n"io" -> {o, u} -> 2.\n"iu" -> {u} -> 1.\n"oo" -> {o, u} -> 2.\n"ou" -> {u} -> 1.\n"uu" -> {u} -> 1.```\n```\n\n\nHence in total, there would be -\n\n```\n5 + 4 + 3 + 2 + 1 +\n4 + 3 + 2 + 1 +\n3 + 2 + 1 +\n2 + 1 +\n1 \n= 35 \n```\n\n\nYou can also try the above pattern n = 2.\n\nHere is the very simple code. It can certainly be optized with a mathematical formula.\nI kept it as is considering that n is very small anyway and not everyone would know the\nformula.\n\n```\nclass Solution {\npublic:\n    int countVowelStrings(int n) {\n        int ans = 0;\n        for (int j=1; j<=(n+1); j++) {\n            int sum = 0;\n            for (int i=1; i<=j; i++) {\n                sum += i;\n                ans += sum;\n            }\n        }\n        return ans;\n    }\n};\n```\n\n\n
[]