[Python] Single pass DP | O(N) Time | O(1) Space
Building our Intuition:\nLet us imagine pressedKeys is "2222".\n\nThe only way to interpret "2" is:\n["a"]\n\nThere are two ways we interpret "22":\n["aa", "b"]
**Building our Intuition:**\nLet us imagine pressedKeys is "2222".\n\nThe only way to interpret "2" is:\n["a"]\n\nThere are two ways we interpret "22":\n["aa", "b"]\n\nFour ways we interpret "222":\n["aaa", "ba", "ab", "c"]\n\n7 ways we interpret "2222":\n["aaaa", "baa", "aba", "ca", "aab", "bb", "ac"]\n\nIn each state we can see that to get the ways a digit is interpretting as ending with "a", we need to combine all digits that ended previously with "a", "b", & "c". Then to get the ways the str can be interpretted as ending with "b", it would be the number of strings that ended with "b" in our previous digit. Similarly for "c" we need to get the number of ways the previous str ended with "b".\n\n**So how do we calculate one state from another?**\nSo for the digit "2" in every subsequent digit of "2" to get the new combinations we just check how many previous digits ended with "a", "b", & "c". Same idea goes for every other digit except for "7" and "9" in which case there are 4 transitions, so we need to account and check for one more digit.\n\nWhen we see a new digit, i.e. if after seeing "222" we then encounter a "3", then we reset our states to be all 0, and make our first state to be the combination of all the previous state endings. Meaning if we had "222" then the possible combinations we have is ["aaa", "ba", "ab", "c"], however whenever we encounter a "3", then they all must end with "d", and as such we now get ["aaad", "bad", "abd", "cd"]. Which then is repersented as [4, 0, 0], meaning we have 4 digits that end with "d", and 0 digits that end "e" & "f".\n\n\n```\nclass Solution:\n    def countTexts(self, pressedKeys: str) -> int:\n        if not pressedKeys:\n            return 0\n        \n        MOD = 10 ** 9 + 7\n        chars_in_digit = {\'2\': 3, \'3\': 3, \'4\': 3, \'5\': 3, \'6\': 3, \'7\': 4, \'8\': 3, \'9\': 4}\n        \n        prev_states = [1]\n        prev_digit = None\n        \n        for digit in pressedKeys:\n            total = sum(prev_states) % MOD\n            \n            if digit != prev_digit:\n                prev_states = [total] + [0] * (chars_in_digit[digit] - 1)\n            else:\n                prev_states = [total] + prev_states[:chars_in_digit[digit] - 1]\n                \n            prev_digit = digit\n        \n        return sum(prev_states) % MOD\n```\n\n**TC: O(N)** -> Since all new list creations and tallying of states in each char has an upperbound of 4\n**SC: O(1)** -> Since prev_states has a max length of 4, and other variables are constant
['Dynamic Programming', 'Python']