Counting Valid Key Press Combinations Using Dynamic Programming Memoization
IntuitionThe problem revolves around decoding a sequence of pressed keys on a phone keypad into the possible text combinations. Each digit on the keypad corresp
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
The problem revolves around decoding a sequence of pressed keys on a phone keypad into the possible text combinations. Each digit on the keypad corresponds to multiple letters, and the constraints are:

1. For digits other than '7' and '9', you can press the same key up to 3 times consecutively to form valid combinations.

2. For digits '7' and '9', you can press the same key up to 4 times consecutively.

The goal is to compute the total number of possible ways the given key sequence could represent valid combinations of presses.
# Approach
<!-- Describe your approach to solving the problem. -->
1. Recursive Breakdown:
Starting at a position id in the string pressedKeys, the function tries all valid combinations of consecutive presses based on the rules for each key as possible.

    For every valid group of presses starting at id, the function recursively calculates the combinations for the rest of the string.
2. Base Case:
If id >= n (end of the string), there is exactly 1 valid combination for this sequence.
3. Memoization:
To avoid recalculating results for the same starting index id, the results are stored in a DP array (dp) where dp[id] stores the number of valid combinations starting at index id.

    If dp[id] is not -1, it means the result for that index has already been computed.
4. Transitions:
Always consider pressing the current key exactly once (id + 1).

    If the next key (id + 1) is the same as the current key, consider pressing twice (id + 2).

    If the next two keys (id + 2) are the same, consider pressing three times (id + 3).

    If the current key is '7' or '9' and the next three keys (id + 3) are the same, consider pressing four times (id + 4).

5. Modulo Operation:
Since the result can be very large, the solution takes results modulo  1e9+7 at each step.
# Complexity
- Time complexity: O(n)
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity: O(n)
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```cpp []
class Solution {
public:
    int countTexts(string pressedKeys) {
        int n = pressedKeys.size();
        vector<int> dp(n+1, -1);
        return helper(0, pressedKeys, dp);
    }
    int helper(int id, string &s, vector<int> &dp)
    {
        int n = s.size();
        if(id >= n)
        {
            return 1;
        }
        if(dp[id] != -1)
        {
            return dp[id];
        }
        int mod = 1e9 + 7;
        int ans = 0;
        ans += helper(id+1, s, dp);
        ans %= mod;
        if(id+1 < n && s[id] == s[id+1])
        {
            ans += helper(id+2, s, dp);
            ans %= mod;
        }
        if(id+2 < n && s[id] == s[id+1] && s[id] == s[id+2])
        {
            ans += helper(id+3, s, dp);
            ans %= mod;
        }
        if(id+3 < n && s[id] == s[id+1] && s[id] == s[id+2] && s[id] == s[id+3] && (s[id] == '7' || s[id] == '9'))
        {
            ans += helper(id+4, s, dp);
            ans %= mod;
        }
        dp[id] = ans;
        return ans;
    }
};
```
['Hash Table', 'Math', 'String', 'Dynamic Programming', 'Memoization', 'C++']