Skip to content

3335. Total Characters in String After Transformations I 👍

Approach 1: DP

  • Time: $O(|\texttt{s}| + \log t)$
  • Space: $O(26^2 + 26) = O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
 public:
  int lengthAfterTransformations(string s, int t) {
    constexpr int kMod = 1'000'000'007;
    vector<int> count(26);

    for (const char c : s)
      ++count[c - 'a'];

    while (t-- > 0) {
      vector<int> newCount(26);
      // 'a' -> 'b', 'b' -> 'c', ..., 'y' -> 'z'
      for (int i = 0; i < 25; ++i)
        newCount[i + 1] = count[i];
      // 'z' -> 'ab'
      newCount[0] = count[25];
      newCount[1] = (newCount[1] + count[25]) % kMod;
      count = std::move(newCount);
    }

    return accumulate(count.begin(), count.end(), 0L) % kMod;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
  public int lengthAfterTransformations(String s, int t) {
    final int MOD = 1_000_000_007;
    int[] count = new int[26];

    for (final char c : s.toCharArray())
      ++count[c - 'a'];

    while (t-- > 0) {
      int[] newCount = new int[26];
      // 'a' -> 'b', 'b' -> 'c', ..., 'y' -> 'z'
      for (int i = 0; i < 25; i++)
        newCount[i + 1] = count[i];
      // 'z' -> 'ab'
      newCount[0] = count[25];
      newCount[1] = (newCount[1] + count[25]) % MOD;
      count = newCount;
    }

    return Arrays.stream(count).reduce(0, (a, b) -> (a + b) % MOD);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
  def lengthAfterTransformations(self, s: str, t: int) -> int:
    MOD = 1_000_000_007
    count = [0] * 26

    for c in s:
      count[ord(c) - ord('a')] += 1

    for _ in range(t):
      newCount = [0] * 26
      # 'a' -> 'b', 'b' -> 'c', ..., 'y' -> 'z'
      for i in range(25):
        newCount[i + 1] = count[i]
      # 'z' -> 'ab'
      newCount[0] = count[25]
      newCount[1] = (newCount[1] + count[25]) % MOD
      count = newCount

    return sum(count) % MOD

Approach 2: Matrix

  • Time: $O(|\texttt{s}| + t)$
  • Space: $O(26) = O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
class Solution {
 public:
  int lengthAfterTransformations(string s, int t) {
    // T[i][j] := the number of ways to transform ('a' + i) to ('a' + j)
    const vector<vector<int>> T = getTransformationMatrix();
    const vector poweredT = matrixPow(T, t);
    vector<int> count(26);
    // lengths[i] := the total length of ('a' + i) after t transformations
    vector<long> lengths(26);

    for (const char c : s)
      ++count[c - 'a'];

    for (int i = 0; i < 26; ++i)
      for (int j = 0; j < 26; ++j) {
        lengths[j] += static_cast<long>(count[i]) * poweredT[i][j];
        lengths[j] %= kMod;
      }

    return accumulate(lengths.begin(), lengths.end(), 0L) % kMod;
  }

 private:
  static constexpr int kMod = 1'000'000'007;

  vector<vector<int>> getTransformationMatrix() {
    vector<vector<int>> T(26, vector<int>(26));
    // 'z' -> 'ab'
    T[25][0] = 1;
    T[25][1] = 1;
    // 'a' -> 'b', 'b' -> 'c', ..., 'y' -> 'z'
    for (int i = 0; i < 25; ++i)
      T[i][i + 1] = 1;
    return T;
  }

  vector<vector<int>> getIdentityMatrix(int sz) {
    vector<vector<int>> I(sz, vector<int>(sz));
    for (int i = 0; i < sz; ++i)
      I[i][i] = 1;
    return I;
  }

  // Returns A * B.
  vector<vector<int>> matrixMult(const vector<vector<int>>& A,
                                 const vector<vector<int>>& B) {
    const int sz = A.size();
    vector<vector<int>> C(sz, vector<int>(sz));
    for (int i = 0; i < sz; ++i)
      for (int j = 0; j < sz; ++j)
        for (int k = 0; k < sz; ++k)
          C[i][j] = (C[i][j] + static_cast<long>(A[i][k]) * B[k][j]) % kMod;
    return C;
  }

  // Returns M^n.
  vector<vector<int>> matrixPow(const vector<vector<int>>& M, int n) {
    if (n == 0)
      return getIdentityMatrix(M.size());
    if (n % 2 == 1)
      return matrixMult(M, matrixPow(M, n - 1));
    return matrixPow(matrixMult(M, M), n / 2);
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
class Solution {
  public int lengthAfterTransformations(String s, int t) {
    // T[i][j] := the number of ways to transform ('a' + i) to ('a' + j)
    int[][] T = getTransformationMatrix();
    int[][] poweredT = matrixPow(T, t);
    int[] count = new int[26];
    // lengths[i] := the total length of ('a' + i) after t transformations
    long[] lengths = new long[26];

    for (final char c : s.toCharArray())
      ++count[c - 'a'];

    for (int i = 0; i < 26; ++i)
      for (int j = 0; j < 26; ++j) {
        lengths[j] += (long) count[i] * poweredT[i][j];
        lengths[j] %= MOD;
      }

    return (int) (Arrays.stream(lengths).sum() % MOD);
  }

  private static final int MOD = 1_000_000_007;

  private int[][] getTransformationMatrix() {
    int[][] T = new int[26][26];
    // 'z' -> 'ab'
    T[25][0] = 1;
    T[25][1] = 1;
    // 'a' -> 'b', 'b' -> 'c', ..., 'y' -> 'z'
    for (int i = 0; i < 25; ++i)
      T[i][i + 1] = 1;
    return T;
  }

  private int[][] getIdentityMatrix(int sz) {
    int[][] I = new int[sz][sz];
    for (int i = 0; i < sz; ++i)
      I[i][i] = 1;
    return I;
  }

  // Returns A * B.
  private int[][] matrixMult(int[][] A, int[][] B) {
    final int sz = A.length;
    int[][] C = new int[sz][sz];
    for (int i = 0; i < sz; ++i)
      for (int j = 0; j < sz; ++j)
        for (int k = 0; k < sz; ++k)
          C[i][j] = (int) ((C[i][j] + (long) A[i][k] * B[k][j]) % MOD);
    return C;
  }

  // Returns M^n.
  private int[][] matrixPow(int[][] M, int n) {
    if (n == 0)
      return getIdentityMatrix(M.length);
    if (n % 2 == 1)
      return matrixMult(M, matrixPow(M, n - 1));
    return matrixPow(matrixMult(M, M), n / 2);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Solution:
  def lengthAfterTransformations(self, s: str, t: int) -> int:
    MOD = 1_000_000_007

    def matrixMult(A: list[list[int]], B: list[list[int]]) -> list[list[int]]:
      """Returns A * B."""
      sz = len(A)
      C = [[0] * sz for _ in range(sz)]
      for i in range(sz):
        for j in range(sz):
          for k in range(sz):
            C[i][j] += A[i][k] * B[k][j]
            C[i][j] %= MOD
      return C

    def matrixPow(M: list[list[int]], n: int) -> list[list[int]]:
      """Returns M^n."""
      if n == 0:
        return [[1 if i == j else 0  # identity matrix
                for j in range(len(M))]
                for i in range(len(M))]
      if n % 2 == 1:
        return matrixMult(M, matrixPow(M, n - 1))
      return matrixPow(matrixMult(M, M), n // 2)

    # T[i][j] := the number of ways to transform ('a' + i) to ('a' + j)
    T = self._getTransformationMatrix()
    poweredT = matrixPow(T, t)
    count = [0] * 26
    lengths = [0] * 26

    for c in s:
      count[ord(c) - ord('a')] += 1

    for i in range(26):
      for j in range(26):
        lengths[j] += count[i] * poweredT[i][j]
        lengths[j] %= MOD

    return sum(lengths) % MOD

  def _getTransformationMatrix(self) -> list[list[int]]:
    T = [[0] * 26 for _ in range(26)]
    # 'z' -> 'ab'
    T[25][0] = 1
    T[25][1] = 1
    # 'a' -> 'b', 'b' -> 'c', ..., 'y' -> 'z'
    for i in range(25):
      T[i][i + 1] = 1
    return T