[Python] Start and bars, explained
Actually, this is very classical combinatorical problem, which can be solved, using so-called stars and bars method: https://en.wikipedia.org/wiki/Stars_and_bar
Actually, this is very classical combinatorical problem, which can be solved, using so-called **stars and bars** method: https://en.wikipedia.org/wiki/Stars_and_bars_(combinatorics). Imagine, that we have string `aa..aee..eii..ioo..ouu..u`, where we have some numbers of `a, e, i, o` and `u`. Then we can look at this problem in the following way: we have `n + 4`, places, and on some of them we need to put bars `|`, for example `aaaeeiuu` is corresponding to `***|**|*||**`. So, final number of solutions is number of combinations from `n+4` to `4,` which can be evaluated as `(n+4)!/n!/4!`.\n\n**Complexity**: time and space complexity is `O(1)`, because `n` is small. One quick optimization is to use `(n+4)*(n+3)*(n+2)*(n+1)//24` formula, which will work faster for big `n`, but given problem constraints different is negligible.\n\n```\nclass Solution:\n    def countVowelStrings(self, n):\n        return factorial(4+n)//factorial(4)//factorial(n)\n```\n\nIf you have any questions, feel free to ask. If you like solution and explanations, please **Upvote!**
[]