Easy Space Optimised Tabualar DP
Intuition\n Describe your first thoughts on how to solve this problem. \nUsing the recurrence relations:-\n- curr[j+1]=(curr[j+1]+prev[j])%mod for all i not equ
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nUsing the recurrence relations:-\n- curr[j+1]=(curr[j+1]+prev[j])%mod for all i not equal to 25\n- curr[0]=(curr[0]+prev[j])%mod\n- curr[1]=(curr[1]+prev[j])%mod for i==25\n\nNow return (prev[0]+prev[1]+.....+prev[25])%mod\n# Approach\n<!-- Describe your approach to solving the problem. -->\n```\nvector<int>prev(26,0);\nfor (char c:s)\n    ++prev[c-\'a\'];\n```\n- Create a frequency array of all the letters in the string.\n\n```\nfor(int i=0;i<t;++i)\n{\n    vector<int>curr(26,0);\n    for(int j=0;j<26;++j)\n    {\n        if(j==25)\n        {\n            curr[0]=(curr[0]+prev[j])%mod;\n            curr[1]=(curr[1]+prev[j])%mod;\n        }\n        else\n            curr[j+1]=(curr[j+1]+prev[j])%mod;\n    }    \n    prev=curr;\n}\n```\n- Now when j!=25 i.e. (\'a\'-\'y\'), We basically increment the (j+1)th character by prev[j].\n- Example:- if the character under consideration is b and we exceed it by 12 then it becomes \'n\' so we add 1 to the count of \'n\'.\n- When j==25 then \'z\' turns to \'ab\' hence we exceed the count of \'a\'(curr[0]) as well as the count of \'b\'(curr[1]).\n\n```\nfor(int i=0;i<26;++i)\n    ans=(ans+prev[i])%mod;\nreturn (int)ans;\n```\n\n# Complexity\n- Time complexity:-$O(n+t)$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:$O(26)$ which is just $O(1)$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    long long exp(long long a,long long b,long long c)\n    {\n        long long res=1;\n        a=a%c;   \n        if(a==0) \n            return 0;\n        while(b>0) \n        { \n            if(b&1) \n                res=(res*a)%c; \n            b=b>>1;\n            a=(a*a)%c; \n        } \n        return res;\n    }\n    int lengthAfterTransformations(string s, int t) {\n        //t=t%26;\n        long long mod=1e9+7,ans=0;\n        /*for(int i=0;i<s.size();++i)\n        {\n            int curr=(int)(s[i]-\'a\');\n            curr=curr%26;\n            int trunc=(curr+t)/26;\n            ans=(ans+exp(2,trunc,mod))%mod;\n        }\n        return (int)ans;*/\n        vector<int>prev(26,0);\n        for(char c:s)\n            ++prev[c-\'a\'];\n\n        for(int i=0;i<t;++i)\n        {\n            vector<int>curr(26,0);\n            for(int j=0;j<26;++j)\n            {\n                if(j==25)\n                {\n                    curr[0]=(curr[0]+prev[j])%mod;\n                    curr[1]=(curr[1]+prev[j])%mod;\n                }\n                else\n                    curr[j+1]=(curr[j+1]+prev[j])%mod;\n            }    \n            prev=curr;\n        }\n        for(int i=0;i<26;++i)\n            ans=(ans+prev[i])%mod;\n        return (int)ans;\n    }\n};\n```
['String', 'Dynamic Programming', 'C++']