Faster than 100% submissions in terms of both Time and Space - DP
Code - Recursive with Memoisation\nIn this approach we memoize the results of the subproblems in the dp array such that we don\'t have to re-compute already com
# Code - Recursive with Memoisation\nIn this approach we memoize the results of the subproblems in the dp array such that we don\'t have to re-compute already computed results.\n\n```\nExample: 2223\nEval(2) + Eval(223)\nEval(22) + Eval(23)\nEval(2) + Eval(2) + Eval(23)\n... and so on\n```\n\n### Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nSince we used `dp` array to hold results, we\'re only evaluating for a given `index` once. \n\nT = $$O(n)$$\n\n### Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nSize of `dp` array and the recursion stack which boils down to `n`.\n\nS = $$O(n)$$\n\n```javascript []\n/**\n * @param {string} pressedKeys\n * @return {number}\n */\nconst M = 1e9 + 7;\nconst maxChars = (key) => {\n  switch(key) {\n    case \'7\':\n    case \'9\': return 4;\n    default: return 3;\n  }\n}\n\nvar countTexts = function(pressedKeys) {\n  return helper(pressedKeys, pressedKeys.length, Array(pressedKeys.length).fill(-1), 0);\n};\n\nfunction helper(pressedKeys, n, dp, start) {\n  if(start > n) return 0;\n  if(start === n) return 1;\n  if(dp[start] !== -1) return dp[start];\n  const key = pressedKeys[start];\n  let singlePressComb = helper(pressedKeys, n, dp, start+1);\n  for(let j=start+1; j<Math.min(start+maxChars(key), n) && key === pressedKeys[j]; j++) {\n    const multiplePressComb = helper(pressedKeys, n, dp, j+1);\n    singlePressComb = (singlePressComb + multiplePressComb)%M;\n  }\n  dp[start] = singlePressComb;\n  return singlePressComb;\n}\n```\n\nFurther optimisations can be done to reduce the space complexities even further but the time complexity will still be $$O(n)$$\n\n## Optimisations\n1. **Dynamic Programming (Bottom-Up Approach):**\nInstead of using a recursive top-down approach with memoization, we can use an iterative bottom-up dynamic programming approach. This removes the overhead of recursive calls and can make the solution faster by avoiding the recursive stack.\n\n2. **Space Optimization (Using Rolling Array):**\nInstead of maintaining a full DP array, we can use a sliding window or rolling array technique to reduce the space complexity from $$O(n)$$ to $$O(1)$$, as only the last 3 or 4 states are required to compute the current state. This is because each position only depends on up to `3` or `4` previous positions.\n\n# Code - Iterative with Rolling DP\n```\nconst M = 1e9 + 7;\n\nconst maxChars = (key) => {\n  switch(key) {\n    case \'7\':\n    case \'9\': return 4;\n    default: return 3;\n  }\n};\n\nvar countTexts = function(pressedKeys) {\n  const n = pressedKeys.length;\n  // Initialize the dp array to hold up to max 4 previous values\n  let dp = [1, 0, 0, 0]; // dp[0] is the base case (empty string)\n  \n  for (let i = 1; i <= n; i++) {\n    let key = pressedKeys[i - 1];\n    let maxLength = maxChars(key);\n    let currentWays = 0;\n\n    // Update dp[i] by considering pressing the same key multiple times\n    for (let j = 1; j <= maxLength && i - j >= 0 && pressedKeys[i - j] === key; j++) {\n      currentWays = (currentWays + dp[(i - j) % 4]) % M; // Mod by 4 bcoz we need to map the given index to one of [0-3]\n    }\n\n    // Shift the window (rolling array)\n    dp[i % 4] = currentWays;\n  }\n\n  return dp[n % 4];\n};\n```
['Dynamic Programming', 'Memoization', 'JavaScript']