Recursion + Memoization , C++ with Explanation ✅✅
Approach\n Describe your approach to solving the problem. \nIf a substring contains the same characters (\'22...\', \'9999......\', \'5555......\',.............
# Approach\n<!-- Describe your approach to solving the problem. -->\n**If a substring contains the same characters (\'22...\', \'9999......\', \'5555......\',..............) How many text are possible by this substring**................................\uD83E\uDD14\n\n**Think about the above statement and try to write the code...........**\n\nhere the approach is simple that we are counting the possible text for a substring that has the same characters and multiplying all the results to get all the possible text.\n\n\n```\nFor example:- p = \'222544\'\nsubstring with same characters = \'222\', \'5\', \'44\'\n\'222\' Possible texts:- \'a\', \'ba\', \'ab\', \'c\'(4)\n\'5\' Possible texts:- \'j\'(1)\n\'44\' Possible texts:- \'gg\',\'h\'(2)\n\nNumber of all possible texts = 4 * 1 * 2 = 8\n```\n**Note:-**\nHere you can see that after enumerating the possible text for a substring I removed all the entries from dp as the previous entry of the same character became invalid so I did that.\n\n```\nFor example:- p = \'222322\'\nHere we can see that \'2\' appears in two substrings:-\n          str1 = \'222\' and str2 = \'22\'\n\nWhen enumerating possible text for str-2, all previous entries\nstr-1 became invalid so we need to remove them.\n```\n# Complexity\n- Time complexity:O(N*log(N))\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:O(N)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    map<pair<int,char>,int> dp;\n    int mod = 1e9+7;\n    long long solve(char c,long long n,long long i)\n    {\n        if(i>n) return 0;\n        if(i>=n-1) return 1;\n        if(dp.find({i,c})!=dp.end()) return dp[{i,c}];\n        long long c1 = solve(c,n,i+1);\n        long long c2 = solve(c,n,i+2);\n        long long c3 = solve(c,n,i+3);\n        long long c4 = solve(c,n,i+4);\n\n        if(c==\'7\' || c==\'9\')\n        return dp[{i,c}] = (c1+c2+c3+c4)%mod;\n        \n        return dp[{i,c}] = (c1+c2+c3)%mod;\n    }\n    int countTexts(string p) {\n       long long count = 1,ans = 1;\n       for(int i = 1;i<p.size();i++)\n       {\n           if(p[i]==p[i-1]) count++;\n           if(p[i]!=p[i-1] || i==p.size()-1)\n           {\n               int x = solve(p[i-1],count,0)%mod;\n               dp.clear();\n               ans  = ((ans%mod)*(x%mod))%mod;\n               count = 1;\n           }\n       }\n       return ans%mod;\n    }\n};\n```\n![upvote.jpg](https://assets.leetcode.com/users/images/347a58e4-fc48-4a72-a4dc-b53ecd812bfa_1689747372.1231217.jpeg)\n
['Dynamic Programming', 'Recursion', 'Memoization', 'C++']