Today I have done leetcode's May LeetCoding Challenge with cpp.

May LeetCoding Challenge 14

Description

Total Characters in String After Transformations II

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 109 + 7.

Example 1:

Example 2:

Constraints:

• 1 <= s.length <= 105
• s consists only of lowercase English letters.
• 1 <= t <= 109
• nums.length == 26
• 1 <= nums[i] <= 25

Solution

template<typename T>
std::ostream& operator<<(std::ostream &out, const std::vector<T> &v) {
  if(v.size() == 0) {
    out << "[]" << std::endl;
    return out;
  }
  out << '[' << v[0];
  for(int i = 1; i < v.size(); ++i) {
    out << ", " << v[i];
  }
  out << ']';
  return out;
}
using ll = long long;
vector<vector<ll>> unitMatrix(int sz) {
  vector<vector<ll>> result(sz, vector<ll>(sz));
  for(int i = 0; i < sz; ++i) result[i][i] = 1;
  return result;
}

void multiply(
  const vector<vector<ll>> &a,
  const vector<vector<ll>> &b,
  vector<vector<ll>> &result,
  const int mod
) {
  int rows = result.size();
  int cols = result.front().size();
  int aRows = b.size();

  for(int i = 0; i < rows; ++i) {
    for(int j = 0; j < cols; ++j) {
      result[i][j] = 0;
      for(int k = 0; k < aRows; ++k) {
        result[i][j] += a[i][k] * b[k][j];
        result[i][j] %= mod;
      }
    }
  }
}

void qpow(
  vector<vector<ll>> &base,
  int exp,
  vector<vector<ll>> &result,
  const int mod
) {
  vector<vector<ll>> temp(result);
  while(exp) {
    if(exp & 1) {
      multiply(base, result, temp, mod);
      swap(result, temp);
    }
    multiply(base, base, temp, mod);
    swap(base, temp);
    exp >>= 1;
  }
}
class Solution {
  const int MOD = 1e9 + 7;
public:
  int lengthAfterTransformations(string s, int t, vector<int>& nums) {
    vector<vector<ll>> initial(1, vector<ll>(26));
    vector<vector<ll>> transfer(26, vector<ll>(26));
    for(auto c : s) {
      initial[0][c - 'a'] += 1;
  }
    for(int i = 0; i < 26; ++i) {
      for(int offset = 1; offset <= nums[i]; ++offset) {
        transfer[i][(i + offset) % 26] = 1;
      }
    }
    vector<vector<ll>> temp = unitMatrix(26);
    qpow(transfer, t, temp, MOD);
    vector<vector<ll>> result(initial);
    multiply(initial, temp, result, MOD);
    // cout << temp << endl;
    // cout << result << endl;
    int answer = 0;
    for(int i = 0; i < 26; ++i) {
      answer += result[0][i];
      answer %= MOD;
    }
    return answer;
  }
};

// Accepted
// 536/536 cases passed (338 ms)
// Your runtime beats 66.67 % of cpp submissions
// Your memory usage beats 83.33 % of cpp submissions (41.8 MB)