3 different solutions (backtracking, dynamic programming, math)
\n\nBacktracking solution:\nTime complexity: O(n^5)\nWe try all the possibilities where adding the new vowel doesn\'t break the lexicographic order. For example
\n\n**Backtracking solution:**\n**Time complexity:** `O(n^5)`\nWe try all the possibilities where adding the new vowel doesn\'t break the lexicographic order. For example, if the last character of our actual possibility is \'e\', we can\'t add an \'a\' after it.\n```\ndef count(n, last=\'\'):\n    if n == 0:\n        return 1\n    else:\n        nb = 0\n        for vowel in [\'a\', \'e\', \'i\', \'o\', \'u\']:\n            if last <= vowel:\n                nb += count(n-1, vowel)\n        return nb\n```\n\n\n**Dynamic programming solution:**\n**Time complexity:** `O(n)`\nWe use a dp matrix of n rows and 5 columns (one column for each vowel) where the number of strings of size k that start with a vowel v is the sum of strings of size k-1 with whom we can add the vowel v from the beginning without breaking the order\nWe can add \'a\' before any vowel string without breaking the order, so the number of strings of size k that start with \'a\' is the number of strings of size k-1 that start with \'a\', \'e\', \'i\', \'o\', or \'u\'\nWe can add \'e\' before strings that start with \'e\', \'i\', \'o\', or \'u\' without breaking the order, so the number of strings of size k that start with \'e\' is the number of strings of size k-1 that start with \'e\', \'i\', \'o\', or \'u\'\nSame logic with remaining vowels (\'i\' -> \'i\', \'o\', or \'u\' / \'o\' -> \'o\' or \'u\' / \'u\' -> \'u\')\nAfter filling the matrix, the last row will contain the numbers of strings of size n with each vowel, we do the sum\n```\ndef count(n):\n    NB_VOWELS = 5\n    dp = [[0]*NB_VOWELS for i in range(n)]\n    dp[0] = [1]*NB_VOWELS\n    for i in range(1, len(dp)):\n        dp[i][0] = dp[i-1][0] + dp[i-1][1] + dp[i-1][2] + dp[i-1][3] + dp[i-1][4] # a\n        dp[i][1] = dp[i-1][1] + dp[i-1][2] + dp[i-1][3] + dp[i-1][4] # e\n        dp[i][2] = dp[i-1][2] + dp[i-1][3] + dp[i-1][4] # i\n        dp[i][3] = dp[i-1][3] + dp[i-1][4] # o\n        dp[i][4] = dp[i-1][4] # u\n    return sum(dp[-1])\n```\n\n\n**Math solution:**\n**Time complexity:** `O(1)`\nThe number of possible sorted strings that we can get by taking n vowels from 5 possible vowels is the number of possible combinations with repetition that we can get by taking n elements from 5 possible elements, and we have a mathematical law for that\n\n![image](https://assets.leetcode.com/users/images/e2537376-77ad-4a4d-be05-07c99acad58d_1620271631.6924222.png)\n\n```\ndef count(n):\n    return (n+4)*(n+3)*(n+2)*(n+1)//24\n```\n\n\n\n\n\n
['Math', 'Dynamic Programming', 'Backtracking', 'Python', 'Python3']