[Java/Python 3] 1 pass O(n) O(1) DP codes w/ explanation, analysis and similar problem.
A Similar problem: \n91. Decode Ways\n\n----\n\n1. If the digit at index i was pressed just 1 times, then the corresponding solution is same as that of the subp
A Similar problem: \n[91. Decode Ways](https://leetcode.com/problems/decode-ways/description/)\n\n----\n\n1. If the digit at index `i` was pressed just `1` times, then the corresponding solution is same as that of the subproblem of `i - 1`; e.g.,\n\n *   7   7   7  (7)\n\n2. If the digit at index `i` was acutally pressed `2` times, then the corresponding solution is same as that of the subproblem of `i - 2`; e.g.,\n\n*   7   7  (7   7)\n\n3.  If the digit at index `i` was acutally pressed `3` times, then the corresponding solution is same as that of the subproblem of `i - 3`; e.g.,\n\n *   7  (7   7   7)\n\n4.  If the digit at index `i` is `7` or `9` and was acutally pressed `4` times, then the corresponding solution is same as that of the subproblem of `i - 4`; e.g.,\n\n *  (7   7   7   7)\n\nCombine the above 4 cases, we can use `dp[i]` to indicate the solution of `pressedKeys.substring(0, i)`, and the general DP transition function is as follows:\n```text\ndp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3] + dp[i - 4]\n```\n\n----\n\n```java\n    private static final int MOD = 1_000_000_007;\n    public int countTexts(String pressedKeys) {\n        int n = pressedKeys.length();\n        int[] dp = new int[n + 1];\n        dp[0] = 1;\n        for (int i = 1; i <= n; ++i) {\n            char c = pressedKeys.charAt(i - 1);\n            dp[i] = dp[i - 1];\n            if (i >= 2) {\n                if (c == pressedKeys.charAt(i - 2)) {\n                    dp[i] = (dp[i] + dp[i - 2]) % MOD; \n                    if (i >= 3 && c == pressedKeys.charAt(i - 3)) {\n                        dp[i] = (dp[i] + dp[i - 3]) % MOD;\n                        if ((c == \'7\' || c == \'9\') && i >= 4 && c == pressedKeys.charAt(i - 4)) {\n                            dp[i] = (dp[i] + dp[i - 4]) % MOD;\n                        }\n                    }\n                }\n            }\n        }\n        return dp[n];\n    }\n```\n```python\n    def countTexts(self, p: str) -> int:\n        dp = [1] + [0] * len(p)\n        for i, c in enumerate(p, 1):\n            dp[i] = dp[i - 1]\n            if i >= 2:    \n                if c == p[i - 2]:\n                    dp[i] += dp[i - 2]\n                    if i >= 3 and c == p[i - 3]:\n                        dp[i] += dp[i - 3]\n                        if c in (\'7\', \'9\') and i >= 4 and c == p[i - 4]:\n                            dp[i] += dp[i - 4]\n            dp[i] %= 10 ** 9 + 7        \n        return dp[len(p)]\n```\n**Analysis:**\nTime & space: `O(n)`, where `n = pressedKeys.length()`.\n\n----\n\nAfter space optimization:\n\n```java\n    private static final int MOD = 1_000_000_007;\n    public int countTexts(String pressedKeys) {\n        int n = pressedKeys.length();\n        int[] dp = new int[5];\n        dp[0] = 1;\n        for (int i = 1; i <= n; ++i) {\n            char c = pressedKeys.charAt(i - 1);\n            int idx = i % 5;\n            dp[idx] = dp[(i - 1) % 5];\n            if (i >= 2) {\n                if (c == pressedKeys.charAt(i - 2)) {\n                    dp[idx] = (dp[idx] + dp[(i - 2) % 5]) % MOD; \n                    if (i >= 3 && c == pressedKeys.charAt(i - 3)) {\n                        dp[idx] = (dp[idx] + dp[(i - 3) % 5]) % MOD;\n                        if ((c == \'7\' || c == \'9\') && i >= 4 && c == pressedKeys.charAt(i - 4)) {\n                            dp[idx] = (dp[idx] + dp[(i - 4) % 5]) % MOD;\n                        }\n                    }\n                }\n            }\n        }\n        return dp[n % 5];\n    }\n```\n```python\n    def countTexts(self, pressedKeys: str) -> int:\n        dp = [1] + [0] * 4\n        for i, c in enumerate(pressedKeys, 1):\n            dp[i % 5] = dp[(i - 1) % 5]\n            if i >= 2:    \n                if c == pressedKeys[i - 2]:\n                    dp[i % 5] += dp[(i - 2) % 5]\n                    if i >= 3 and c == pressedKeys[i - 3]:\n                        dp[i % 5] += dp[(i - 3) % 5]\n                        if c in (\'7\', \'9\') and i >= 4 and c == pressedKeys[i - 4]:\n                            dp[i % 5] += dp[(i - 4) % 5]\n            dp[i % 5] %= 10 ** 9 + 7        \n        return dp[len(pressedKeys) % 5]\n```\n\nSimplify the above codes further:\n\n```java\n    private static final int MOD = 1_000_000_007;\n    public int countTexts(String pressedKeys) {\n        int n = pressedKeys.length();\n        int[] dp = new int[5];\n        dp[0] = 1;\n        for (int i = 1; i <= n; ++i) {\n            char c = pressedKeys.charAt(i - 1);\n            int idx = i % 5, lowBound = Math.max(0, i - (c == \'7\' || c == \'9\' ? 4 : 3));\n            dp[idx] = dp[(i - 1) % 5];\n            for (int j = i - 2; j >= lowBound && c == pressedKeys.charAt(j); --j) {\n                dp[idx] = (dp[idx] + dp[j % 5]) % MOD; \n            }\n        }\n        return dp[n % 5];\n    }\n```\n```python\n    def countTexts(self, pressedKeys: str) -> int:\n        dp = [1] + [0] * 4\n        for i, c in enumerate(pressedKeys, 1):\n            dp[i % 5] = dp[(i - 1) % 5]\n            for j in range(i - 2, max(-1, i - 4 - (c in \'79\')), -1):\n                if c == pressedKeys[j]:\n                    dp[i % 5] += dp[j % 5]\n                else:\n                    break    \n            dp[i % 5] %= 10 ** 9 + 7        \n        return dp[len(pressedKeys) % 5]\n```\n**Analysis:**\nTime: `O(n)`, space: `O(1)`, where `n = pressedKeys.length()`.
[]