Easy Recursion + Memoization O(26*n) solution C++ ✅
Intuition\nSince we can have only 26 distinct characters, if we pre-calculate the length for each alphabet, we can just add all to reach to ans;\n# Approach\nWh
# Intuition\nSince we can have only 26 distinct characters, if we pre-calculate the length for each alphabet, we can just add all to reach to ans;\n# Approach\nWhen you try to transform the character \'a\' it eventually become \'z\' and then \'ab\' which can be solved independently for \'a\' and \'b\' using recursion. So we can directly use recursion here with memoization to store the answer.\n\n# Complexity\n- Time complexity:\n$$O(n*26) = O(n)$$\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    int dp[26][100001];\n    int MOD = 1e9 + 7;\n    int getLength(char c, int t) {\n        if(t == 0)\n            return 1;\n        if(dp[c-\'a\'][t] != -1)\n            return dp[c-\'a\'][t];\n        if(c == \'z\') {\n            return dp[c-\'a\'][t] = (getLength(\'a\',t-1) % MOD + getLength(\'b\',t-1) % MOD) % MOD;\n        }\n        return dp[c-\'a\'][t] = getLength(c+1, t-1);\n    }\n    int lengthAfterTransformations(string s, int t) {\n        memset(dp,-1,sizeof(dp));\n        int ans = 0;\n        for(char c : s) {\n            ans = (ans + getLength(c,t)) % MOD;\n        }\n        return ans;\n    }\n};\n```
['C++']