C++ O(t) Beats 100.00% 4ms solution
Intuition\nImprove O(t26) solution from\nhttps://leetcode.com/problems/total-characters-in-string-after-transformations-i/solutions/5972920/string-evolution-the
# Intuition\nImprove $$O(t*26)$$ solution from\nhttps://leetcode.com/problems/total-characters-in-string-after-transformations-i/solutions/5972920/string-evolution-the-transformation-challenge-easy-cpp-hashing-solution/ to $$O(t)$$.\nFor every 26 transformations, `a` becomes `ab`, `b` becomes `bc`, ..., `y` becomes `yz`.\n`z` becomes `zab`.\n\n# Approach\nFor every 26 transformations in t:\n  - For characters between `a` and `y`, add the character count to the next character.\n  - For `z`, add `z`\'s count to `a` and `b`.\n\nThis part takes $$O(t/26*26)=O(t)$$ time.\n\nFor the remaining transformations less than 26, just apply the $$O(t*26)$$ solution which takes $$O(25*26)=O(650)$$ time.\n\nSum the count takes $$O(26)$$ time.\n\n# Complexity\n- Time complexity:\n$$O(t+650+26)=O(t)$$\n\n- Space complexity:\n$$O(26)$$ for character count\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    int lengthAfterTransformations(string s, int t) {\n        const auto mod = 1000000007;\n        int count[26] = {0};\n        for (auto c : s) {\n            ++count[c - \'a\'];\n        }\n        for (; t >= 26; t -= 26) {\n            auto z = count[25];\n            for (auto i = 25; i > 0; --i) {\n                count[i] += count[i - 1];\n                count[i] %= mod;\n            }\n            count[0] += z;\n            count[0] %= mod;\n            count[1] += z;\n            count[1] %= mod;\n        }\n        for (; t > 0; --t) {\n            auto z = count[25];\n            for (auto i = 25; i > 0; --i) {\n                count[i] = count[i - 1];\n            }\n            count[0] = z;\n            count[1] += z;\n            count[1] %= mod;\n        }\n        auto ans = 0;\n        for (auto c : count) {\n            ans += c;\n            ans %= mod;\n        }\n        return ans;\n    }\n};\n```\n\n# Another O(t) Solution\nFrom https://leetcode.com/problems/total-characters-in-string-after-transformations-i/solutions/5973137/java-clean-solution/\n\nThis is actually equivalent to the approach in https://leetcode.com/problems/total-characters-in-string-after-transformations-i/solutions/5972920/string-evolution-the-transformation-challenge-easy-cpp-hashing-solution/\n\nHowever, instead of shifting all elements right by 1, it moves the pointer to `z` to the left by 1. Therefore, the time complexity is reduced from $$O(t*26)$$ to $$O(t)$$.\n\nThe variable `i` is the pointer to `z`.\n\n## Example\n\nInitial:\ni = 25\n\ncount:\na b ... y z\n2 3 ... 5 7\n\nTransform once:\n\nshift right:\nb c ... z a\n2 3 ... 5 7\n\nadd `z` count before shifting to `b` count after shifting:\n`z` count before shifting is `count[i]` = `count[25]` = 7\n`b` position after shifting is `(i + 1) % 26` = 0\n\nthen we have:\nb c ... z a\n9 3 ... 5 7\n\nupdate the pointer to `z`:\n`i = (i - 1 + 26) % 26` equivalent to `i = (i + 25) % 26` = 24\nThe `+ 26` is to make `i` nonnegative.\n\n## Code Rewritten in C++\n\n```cpp []\nclass Solution {\npublic:\n    int lengthAfterTransformations(string s, int t) {\n        const auto mod = 1000000007;\n        int count[26] = {0};\n        for (auto c : s) {\n            ++count[c - \'a\'];\n        }\n        for (auto i = 25; t > 0; --t, i = (i + 25) % 26) {\n            auto j = (i + 1) % 26;\n            count[j] += count[i];\n            count[j] %= mod;\n        }\n        auto ans = 0;\n        for (auto c : count) {\n            ans += c;\n            ans %= mod;\n        }\n        return ans;\n    }\n};\n```
['C++']