C++ | Linear time, constant space solution
Simple Inputs\n\n#### Example 1.1: "23578"\n\nQ: What if we don\'t have repetitions in the input string?\n\nA: Our fingers just press each key once to produce t
## Simple Inputs\n\n#### Example 1.1: "23578"\n\nQ: What if we don\'t have repetitions in the input string?\n\nA: Our fingers just press each key once to produce the message.\n\n> The answer is 1\n\n#### Example 1.2: "235782783578"\n\nQ: What if we do have some same digit appear across the input string?\n\nA: As long as they are not back-to-back grouping with their own kinds,\nour fingers still need to press each key once and move around for another.\n\n> The answer is still 1\n\n#### Short Summary\n\nIn examples 1.x, things are simple. \nWe can safely assume \n\n> finger movement **must** occur between **all** adjacent keys\n\nand hence one-and-only-one message can be incurred from each of these input strings.\n\n## Fancy Inputs\n\nAs the problem suggest, we may have same digit in some groups of contiguous substring.\n\nWe somehow still want the observation in examples 1.x to happen here.\nExcept that this time, we can only do \n\n> finger movement **may** occur between **some** adjacent keys\n\nConsidering this, we may want to cut `"22233"` into `"222"` and `"33"`.\n\n**Q: How exactly is `count("22233")` and `count("222")` and `count("33")` are related?**\n\n#### Example 2: "22233"\n\nSince our finger shall jump between `2` and `3` at some point,\nLet\'s say we press `222` and form `ba`.\n**Then we must break the continuity and switch keys** (from `2` to `3`).\nNext, pressing `33` can give a `e`.\nThe final message `bae` is then formed by concatenating the pre-chosen segments.\n\nMore precisely, \neach of the possible outcome from `222` can be paired with an outcome from `33` \nfor producing a possible message.\n\nThus, the Product Rule (from Discrete Maths) applies.\n\n```\ncount("22233")   =   count("222")   \xD7   count("33")\n```\n\n## Extract Subroutine\n\nWe can imagine how the product expands, when more **contiguous substrings of same character** present.\n\nSay we extract out a subroutine for solving contiguous substrings of this kind, \n\n```c++\nint countSameTexts(char& cc, int& count);\n```\n\nthen we can formulate our solver progam as below. \n\n```c++\nclass Solution {\npublic:\n    long modulo = 1000000007;\n    int countSameTexts(char& cc, int& count);\n    int countTexts(string pressedKeys) {\n        long res = 1;\n        int count = 0;\n        char current = pressedKeys[0];\n        for (char& c: pressedKeys)\n            /* Accumulate count for contiguous substrings of same character */\n            if (current == c)\n                count++;\n            /* Update `res` by Product Rule and `modulo` during key-switch */\n            else {\n                res = (res * countSameTexts(current, count)) % modulo;\n                current = c;\n                count = 1; // Reset count\n            }\n        /* Update `res` one final time */\n        return (res * countSameTexts(current, count)) % modulo;\n    }\n};\n```\n\n## Construct Subroutine By Dynamic Programming\n\n### Case 1: 7, 9\n\n#### Arbitrary length n\nFrom the given repetition rule, a string with length `n` can be formed by one of the following.\n- character formed by subtring of length `1` + chracters from remaining substrings of length `(n - 1)`\n- character formed by subtring of length `2` + chracters from remaining substrings of length `(n - 2)`\n- character formed by subtring of length `3` + chracters from remaining substrings of length `(n - 3)`\n- character formed by subtring of length `4` + chracters from remaining substrings of length `(n - 4)`\n\nSub-optimal property is obviously preserved, \nsince any length of substring from the original string always contains the same character.\n\nThe above events are disjoint and exhaustive.\nThus, the Sum Rule (from Discrete Maths) applies.\n\n```\nCount_79(n)   =   Count_79(n - 1)   +   Count_79(n - 2)   +   Count_79(n - 3)   +   Count_79(n - 4)\n```\n\n#### Base Case of length 1, 2, 3, 4\n\nFor `n = 1`, obviously `Count_79(2) = 1`.\n\nFor `n = 2`, we have `7, 7` or `77`. so `Count_79(2) = 2`.\n\nFor `n = 3`, we have `7, 7, 7` or `7, 77` or `77, 7` or `777`. so `Count_79(3) = 4`.\n\nFor `n = 4`, the count will involve\n- 1 permutation involving `7`\n- 3 permutation involving `7` and `77`\n- 2 permutation involving `7` and `777`\n- 1 permutation involving `77` and `77`\n- 1 permutation involving `7777`\nHence, `Count_79(4) = 8`.\n\n#### Complete Formula \n\nFrom base case and recursion, we can obtain the complete formula ... (1)\n\n```\nCount_79(1)   =   1\nCount_79(2)   =   2\nCount_79(3)   =   4\nCount_79(4)   =   8\nCount_79(n)   =   Count_79(n - 1)   +   Count_79(n - 2)   +   Count_79(n - 3)   +   Count_79(n - 4)\n```\n\n### Case 2: 2, 3, 4, 5, 6, 8\n\n#### Complete Formula \n\nFollow a similar analysis as above, we can have the below formula ... (2)\n\n(Can you deduce the details?)\n\n```\nCount_234568(1)   =   1\nCount_234568(2)   =   2\nCount_234568(3)   =   4\nCount_234568(n)   =   Count_234568(n - 1)   +   Count_234568(n - 2)   +   Count_234568(n - 3)\n```\n\n### Code\n\nThe code can easily be written, with bottom-up DP.\n\n```c++\nint Solution::countSameTexts(char& cc, int& count) {\n    // Count for 7, 9\n    if (cc == \'7\' || cc == \'9\') {\n        if (count <= 4)\n            return 1 << (count - 1);\n        long a = 1 << 0;\n        long b = 1 << 1;\n        long c = 1 << 2;\n        long d = 1 << 3;\n        for (int i = 4; i < count; i++) {\n            long new_a = b;\n            long new_b = c;\n            long new_c = d;\n            long new_d = (a + b + c + d) % modulo;\n            a = new_a;\n            b = new_b;\n            c = new_c;\n            d = new_d;\n        }\n        return d;\n    }\n    // Count for 2, 3, 4, 5, 6, 8\n    else {        \n        if (count <= 3)\n            return 1 << (count - 1);\n        long a = 1 << 0;\n        long b = 1 << 1;\n        long c = 1 << 2;\n        for (int i = 3; i < count; i++) {\n            long new_a = b;\n            long new_b = c;\n            long new_c = (a + b + c) % modulo;\n            a = new_a;\n            b = new_b;\n            c = new_c;\n        }\n        return c;\n    }\n}\n```\n\n## Possible Optimization\n\nFormula in (1) and (2) can easily be speed-up to logarithmic cost, by (binary) exponetiation of matrix.\nI invite readers to develop a fancy (or somewhat standard) program with this approach :)\n
['Dynamic Programming', 'Counting']