[Java] Solution + Intuition behind every possible DP solution here of this problem!
Let\'s take a generic example where we need to make n character long sorted stings :-\n[When I am telling first or second char then it is counted from right]\n\
Let\'s take a generic example where we need to make n character long sorted stings :-\n*[When I am telling first or second char then it is counted from right]*\n\nNow the possible strings possible for **n = 1** is :- a, e, i, o, u\n\nNow for **n = 2**, \nif the first character from end was \'a\' then the second char must be \'a\' only, right. [1 string possible]\nSimilarly, if the first character from end was \'e\' then the second char can be \'a\' and \'e\'. \n[2 strings possible]\nSimilarly, if the first character from end was \'i\' then the second char can be \'a\', \'e\' and \'i\'.\n[3 strings possible]\nSimilarly, if the first character from end was \'o\' then the second char can be \'a\', \'e\', \'i\' and \'o\'.\n[4 strings possible]\nSimilarly, if the first character from end was \'u\' then the second char can be \'a\', \'e\', \'i\', \'o\' and \'u\'.\n[5 strings possible]\n\n[At next Index from right i.e. At 2nd index]\n**a->** can be produced by all strings (As we have total 5 strings, Therefore 5)\n**e->** can be produced by all strings except which ends with \'a\'\n**i->** can be produced by all strings except which ends with \'a\', \'e\'\n**o->** can be produced by all strings except which ends with \'a\', \'e\', \'i\'\n**u->** can be produced by all strings except which ends with \'a\', \'e\', \'i\', \'o\'\n**5 + 4 + 3 + 2 + 1 = 15**\n\nNow for **n = 3**, \nif the second character from end was \'a\' then the third char must be \'a\' only, right. \nNow the possible string with \'a\' at second index when n was 2 is **5** [1*5 string possible]\nAgain take a took at n = 2, when total possible strings have \'a\' five times at index = 2. \n\nSimilary, \'e\' occurs 4 times when n was 2 and \'e\' for prev index will result into 2 possible chars \'a\' and \'e\' at current index, so [2*4 strings possible] \n\nSimilarly for other characters at second index we will have sum:-\n**(15) + (15-5) + (15-5-4) + (15-5-4-3) + (15-5-4-3-2) = 35**\n\nNow in similar fashion you can count possible strings of any length, Right.\nExample: for **n = 4** ->\n**(35) + (35-15) + (35-15-10) + (35-15-10-6) + (35-15-10-6-3) = 70**\n\n```\nclass Solution {\n    public int countVowelStrings(int n) {\n        int[] dp = new int[5]; // It will store count of each char [a, e, i, o, u]\n        Arrays.fill(dp, 1);\n        \n        for(int i = 1; i < n; i++){\n            int sum = 0;\n            for(int j = 0; j < 5; j++){\n                sum += dp[j];\n            }\n            \n            int prev = 0;\n            for(int idx = 0; idx < 5; idx++){\n                int temp = dp[idx];\n                sum -= prev;\n                dp[idx] = sum;\n                prev = temp;\n            }\n        }\n        \n        return dp[0] + dp[1] + dp[2] + dp[3] + dp[4];\n    }\n}\n```\n\nIf it helps you then, Please upvote :)\nSuggestions are most welcome. :D
[]