[LeetCode] 3337. Total Characters in String After Transformations II

https://leetcode.com/problems/total-characters-in-string-after-transformations-ii/description/?envType=daily-question&envId=2025-05-14

leetcode - Total Characters in String After Transformations

문제 유형: 행렬 거듭제곱, 문자열 처리, 선형변환

문제 난이도: Hard

문제

You are given a string s consisting of lowercase English letters, an integer t representing the number of transformations to perform, and an array nums of size 26. In one transformation, every character in s is replaced according to the following rules:

• Replace s[i] with the next nums[s[i] - 'a'] consecutive characters in the alphabet. For example, if s[i] = 'a' and nums[0] = 3, the character 'a' transforms into the next 3 consecutive characters ahead of it, which results in "bcd".
• The transformation wraps around the alphabet if it exceeds 'z'. For example, if s[i] = 'y' and nums[24] = 3, the character 'y' transforms into the next 3 consecutive characters ahead of it, which results in "zab".

Return the length of the resulting string after exactly t transformations.

Since the answer may be very large, return it modulo 10^9 + 7.

 

영문소문자로 된 문자열 s가 주어진다.

변환 횟수인 정수 t가 주어지고, 26길이의 nums배열이 주어진다.

다음의 규칙을 따라야 한다:

s[i]를 nums[s[i]-'a']로 바꿔라. 만약 z를 넘는다면, 'ab'로 바꾸고 각각에 남은 변환수만큼 적용하라.

 

t번의 변환 후의 문자열의 길이를 구하시오. 커질 수 있으니, 1e9+7로 나누시오.

 

풀이

t가 매우 크기에, 순수한 연산으로는 불가능하다.

대신, 상태의 수는 매우 작기에, 행렬 거듭제곱을 이용해서 풀 수 있다.

 

선형변환은 new = T * old의 꼴이다.

즉, 정답 = T^t(변환행렬을 t번 전이한것을 반영) * 초기상태이다.

초기상태는 빈도 행렬로 초기화해주면 된다.

 

nums를 기반으로, 인접 행렬을 구성한다. 즉, 상태의 전이에 대한 인접행렬이다.

i번째 알파벳(0 <= i < 26)이 있으면, d:1 ~ nums[i]에 대해서, j = (i+d)%26는 i로부터 전이될 수 있다.

 

이렇게 인접행렬을 구성해준 뒤, 고속 행렬 거듭제곱을 통해서(모르면 코드를 참조하여 이해) 빠르게 전이 행렬을 t제곱까지 해준다.

T제곱된 전이행렬에 초기 상태를 곱하여, 최종 상태를 구하고, 그 합을 모두 더해주면 된다.

 

코드

C++

using ll = long long;
const int MOD = 1e9+7;
class Solution {
public:
    vector<vector<ll>> matMul(vector<vector<ll>> &a, vector<vector<ll>> &b) {
        int n = a.size();
        int m = b[0].size();
        vector<vector<ll>> res(n, vector<ll>(m, 0));

        for(int i = 0; i < n; i++) {
            for(int k = 0; k < a[0].size(); k++) {
                for(int j = 0; j < m; j++) {
                    res[i][j] = (res[i][j] + a[i][k] * b[k][j]) % MOD;
                }
            }
        }

        return res;
    }
    vector<vector<ll>> bpow(vector<vector<ll>> base, ll exp) {
        vector<vector<ll>> res(base.size(), vector<ll>(base.size(), 0));
        for (int i = 0; i < base.size(); ++i) {
            res[i][i] = 1;
        }
        while(exp > 0) {
            if(exp&1) {
                res = matMul(res, base);
            }
            exp >>=1;
            base = matMul(base, base);
        } 
        return res;
    }
    int lengthAfterTransformations(string s, int t, vector<int>& nums) {
        vector<vector<ll>> T(26, vector<ll>(26, 0));
        for (int i = 0; i < 26; i++) {
            for (int d = 1; d <= nums[i]; d++) {
                int j = (i + d) % 26;
                T[i][j] += 1;
            }
        }

        vector<vector<ll>> freq(1, vector<ll>(26, 0));
        for(char ch : s) {
            freq[0][ch-'a']++;
        }
        auto Tt = bpow(T, t);
        auto res = matMul(freq, Tt);
        
        ll ans = 0;
        for(int i = 0; i < 26; i++) {
            ans = (ans + res[0][i]) % MOD;
        }

        return ans;
    }
};

 

Go

const MOD int64 = 1_000_000_007

type Matrix [][]int64
func newMatrix(r, c int) Matrix {
    m := make(Matrix, r)
    for i:= range m {
        m[i] = make([]int64, c)
    }
    return m
}
func matMul(a, b Matrix) Matrix {
    n, m, l := len(a), len(b[0]), len(b)
    res := newMatrix(n, m)
    for i := 0; i < n; i++ {
        for k := 0; k < l; k++ {
            for j := 0; j < m; j++ {
                res[i][j] = (res[i][j] + a[i][k] * b[k][j]) % MOD   
            }
        }
    }
    return res
}
func bpow(base Matrix, exp int64) Matrix {
    n := len(base)
    res := newMatrix(n, n)
    for i := 0; i < n; i++ {
        res[i][i] = 1
    }
    for exp > 0 { 
        if exp%2 == 1 {
            res = matMul(res, base)
        }
        exp >>= 1;
        base = matMul(base, base)
    }

    return res
}

func lengthAfterTransformations(s string, t int, nums []int) int {
    T := newMatrix(26, 26) 
    freq := newMatrix(1, 26)

    for i := 0; i < 26; i++ {
        for d := 1; d <= nums[i]; d++ {
            j := (i + d) % 26
            T[i][j]++
        }
    }
    for _, ch := range s {
        freq[0][ch-'a']++
    }

    Tt := bpow(T, int64(t))
    res := matMul(freq, Tt)

    ans := int64(0)
    for i := 0; i < 26; i++ {
        ans = (ans + res[0][i]) % MOD
    }

    return int(ans)
}