C++ DP Solution O(N)
Runtime: 32 ms, faster than 100.00% of C++ online submissions for Count Number of Texts.\nMemory Usage: 19.3 MB, less than 40.00% of C++ online submissions for 
Runtime: 32 ms, faster than 100.00% of C++ online submissions for Count Number of Texts.\nMemory Usage: 19.3 MB, less than 40.00% of C++ online submissions for Count Number of Texts.\n\n\n```\nWe can calculate the letter combination count of each digit type for different length using DP.\n\nLetter combinations for digit 2,3,4,5,6,8 is same for length  1 to N as they all have 3 letters in their button\n\nBase case combinations: Length 1 to 3\n\nLength 1 => [2] => \'a\' => 1\nLength 2 => [2,2] => \'aa\', \'b\' => 2\nLength 3 =>  [2,2,2] => \'aaa\', \'ab\', \'ba\', \'c\' => 4\n\nNow for Length > 3 we can get combination count from previous length combinations\nLength 4 => [2,2,2,2] => \'aaaa\', \'aab\', \'aba\', \'ac\' , \'baa\' , \'bb\', \'ca\'  => 7\n\nLet first letter as \'a\', which has length 1 => [2]\nThen total letter combination of length 4 with first letter \'a\' is DP[4-1] = DP[3] =>  \'aaaa\', \'aab\', \'aba\', \'ac\' => 4\n\nLet first letter as \'b\', which has length 2 => [2,2]\nThen total letter combination of length 4 with first letter \'b\' is DP[4-2] = DP[2] =>  \'baa\' , \'bb\' => 2\n\nLet first letter as \'c\', which has length 3 => [2,2,2]\nThen total letter combination of length 4 with first letter \'c\' is DP[4-3] = DP[1] =>  \'ca\' => 1\n\nSo, total letter combination of Length 4 => DP[4-1] + DP[4-2] + DP[4-3] = 4 + 2 + 1 = 7 \n\nDP equation: DP[N] => DP[N-1] + DP[N-2] + DP[N-3]\n\nLetter combinations for digit 7 and 9 is same for length  0 to N as they all have 4 letters in their button\n\nBase case combinations: Length 1 to 4\n\nLength 1 => [7] => \'p\' => 1\nLength 2 => [7,7] => \'pp\' or \'q\' => 2\nLength 3 =>  [7,7,7] => \'ppp\', \'pq\', \'qp\', \'r\' => 4\nLength 4 => [7,7,7,7] => \'pppp\', \'ppq\', \'pqp\', \'pr\', \'qq\', \'qpp\', \'rp\', \'s\' => 8\n\nSimilary as above, DP equation: DP[N] => DP[N-1] + DP[N-2] + DP[N-3] + DP[N-4]\n\nFirst we get the max frequency of each digit and their frequency chunks.\nThen we generate letter combinations for 0 to max frequency of each digit in DP\nThen we multiply the DP[X] of frequency chunks X of each digit as their letter combinations are independent.\n```\n\n\n\n```\nclass Solution {\npublic:\n    int countTexts(string pressed) {\n        \n        int MOD = 1000000007;\n        int pl = pressed.length();\n        \n        // base case combinations for 2-9 digits of length 0 to 4\n        vector<vector<int>>preDP = {{0,1,2,4},{0,1,2,4,8}};\n            \n        // store max freq of each digit and freq chunks\n        int maxFreq[10] = {};\n        vector<int>freq[10];\n        \n        int curr = -1;\n        int count = 0;\n        \n        for(int i=0;i<pl;i++)\n        {\n            if(pressed[i]-\'0\' == curr)\n            {\n                count++;\n                maxFreq[curr] = max(maxFreq[curr],count);\n                freq[curr].back()++;\n            }\n            else\n            {\n                curr = pressed[i]-\'0\';\n                count = 1;\n                maxFreq[curr] = max(maxFreq[curr],count);\n                freq[curr].push_back(count);\n            }\n        }\n        \n        vector<long long>dp(pl+1);\n        unsigned long long totalCount = 1L;\n        int type;\n        for(int i=0;i<10;i++)\n        {\n            if(maxFreq[i]==0)continue;\n            \n            // get digit type\n            type = (i==7 || i==9) ? 1 : 0;\n            \n            // store the base case combinations for length 0 to 4\n            for(int j=0;j<=maxFreq[i] && j<=3+type;j++)\n                dp[j] = preDP[type][j];\n            \n            // store combinations for length 5 to max freq of current digit \n            for(int j=4+type;j<=maxFreq[i];j++)\n                dp[j] = (dp[j-1]  + dp[j-2] + dp[j-3] + (type ? dp[j-4] : 0) + MOD)%MOD;\n            \n            // get the digit freq chunk multiplications as they are independent\n            for(int j=0;j<freq[i].size();j++)\n                totalCount = (totalCount%MOD * dp[freq[i][j]]%MOD) %MOD ;  \n        }\n        \n        return (int)totalCount;\n    }\n};\n```\n\n\n\n\n\n
['Dynamic Programming', 'C', 'Combinatorics']