[Leetcode] 3335. Total Characters in String After Transformations I

https://leetcode.com/problems/total-characters-in-string-after-transformations-i/solutions/5972920/string-evolution-the-transformation-challenge-easy-cpp-hashing-solution/?envType=daily-question&envId=2025-05-13

initial

there was a very obvious way to simulate increasing t but I knew there is a better way (turns out it can be dp). But even with simulation i still couldnst solve it like i get wrong ans for big t

even when i put long instead of int i get wrong tc

class Solution {
    public int lengthAfterTransformations(String s, int t) {
        // Initial frequency map
        Map<Character, Long> map = new HashMap<>();
        for (char c : s.toCharArray()) {
            map.put(c, map.getOrDefault(c, 0L) + 1);
        }
        
        // Perform transformations
        while (t > 0) {
            Map<Character, Long> nextMap = new HashMap<>();
            for (Map.Entry<Character, Long> entry : map.entrySet()) {
                char c = entry.getKey();
                long count = entry.getValue();
                
                if (c == 'z') {
                    // 'z' becomes "ab"
                    nextMap.put('a', nextMap.getOrDefault('a', 0L) + count);
                    nextMap.put('b', nextMap.getOrDefault('b', 0L) + count);
                } else {
                    // Any other character becomes the next character
                    char next = (char) (c + 1);
                    nextMap.put(next, nextMap.getOrDefault(next, 0L) + count);
                }
            }
            map = nextMap;
            t--;
            
            // Optimization: If t is large, we can detect cycles
            // For this problem, we'd need to analyze the pattern carefully
        }
        
        // Calculate final length
        long length = 0;
        final int MOD = 1000000007;
        for (long count : map.values()) {
            length = (length + count) % MOD;
        }
        
        return (int) length;
    }
}

sol

so using map seems to have a problem. Instead lets just use a int[26] size and update the freq of each alphabet along the way.

the logic is for each t simulation, we carry forward previous alphabet frequency. Like if its c and with this t simulation we need to change to t, it should be count[c] + tmp[d].

But if its z, we need to carry forward all the z to the transformed a and b each. So it is
if char is z (i.e. i==25)
tmp[0] = (tmp[0] + count[i]) % MOD;
tmp[1] = (tmp[1] + count[i]) % MOD;

class Solution {
    public int lengthAfterTransformations(String s, int t) {
        long[] count = new long[26];
        final int MOD = 1000000007;
        for (char c : s.toCharArray()) {
            count[c-'a']+=1;
        }
        while (t > 0) {
            long[] tmp = new long[26];
            for (int i=0; i<26; i++) {
                if(i==25){
                    tmp[0]=(tmp[0]+count[i])%MOD;
                    tmp[1]=(tmp[1]+count[i])%MOD;
                }
                else{
                    tmp[i+1]=(tmp[i+1]+count[i])%MOD;
                }
            }
            count = tmp;
            t--;
        }
        // Calculate final length
        long length = 0;
        for (long i : count) {
            length = (length +i) % MOD;
        }
        
        return (int) length;
    }
}

dp

there is a carry on pattern where we reuse previous frequencies

i should have known we could use dp

    private int mod = 1000000007;
    private int[] dp = new int[100100];

    public Solution() {
        for (int i = 0; i < 26; ++i)
            dp[i] = 1;
        for (int i = 26; i < 100100; ++i)
            dp[i] = (dp[i - 26] + dp[i - 26 + 1]) % mod;
    }

    public int lengthAfterTransformations(String s, int t) {
        int res = 0, n = s.length();
        for (int i = 0; i < n; ++i)
            res = (res + dp[s.charAt(i) - 'a' + t]) % mod;
        return res;
    }

complexity

n+t time
26 space so 1 space