Similar to 552
IntuitionSame type of question as this:
https://leetcode.com/problems/student-attendance-record-ii/description/ApproachFigure out the transition matrix. Be care
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nSame type of question as this:\nhttps://leetcode.com/problems/student-attendance-record-ii/description/\n# Approach\n<!-- Describe your approach to solving the problem. -->\nFigure out the transition matrix. Be careful of whether adding \'l\', \'e\' and \'t\' would transition to another state.\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(log n)$$\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(1)$$\n# Code\n```python3 []\n#\n# @lc app=leetcode id=2930 lang=python3\n#\n# [2930] Number of Strings Which Can Be Rearranged to Contain Substring\n#\n\n# @lc code=start\nclass Solution:\n    def matrix_multiply(self, A, B, MOD):\n        m = len(A)\n        n = len(B[0])\n        C = [[0 for i in range(n)] for j in range(m)]\n        for i in range(m):\n            for k in range(n):\n                for j in range(len(B)):\n                    C[i][k] += A[i][j]*B[j][k]\n                    C[i][k] %= MOD\n        return C\n    \'\'\'\n    dp[i][0] = number of strings of length i + 1 that contains ""\n    dp[i][1] = number of strings of length i + 1 that contains "l"\n    dp[i][2] = number of strings of length i + 1 that contains "e"\n    dp[i][3] = number of strings of length i + 1 that contains "t"\n    dp[i][4] = number of strings of length i + 1 that contains "le"\n    dp[i][5] = number of strings of length i + 1 that contains "et"\n    dp[i][6] = number of strings of length i + 1 that contains "lt"\n    dp[i][7] = number of strings of length i + 1 that contains "ee"\n    dp[i][8] = number of strings of length i + 1 that contains "lee"\n    dp[i][9] = number of strings of length i + 1 that contains "let"\n    dp[i][10] = number of strings of length i + 1 that contains "eet"\n    dp[i][11] = number of strings of length i + 1 that contains "leet"\n    We have this recurrence relation:\n    dp[i + 1][0] = 23 * dp[i][0]\n    dp[i + 1][1] = 24 * dp[i][1] + dp[i][0]\n    dp[i + 1][2] = 23 * dp[i][2] + dp[i][0]\n    dp[i + 1][3] = 24 * dp[i][3] + dp[i][0]\n    dp[i + 1][4] = 24 * dp[i][4] + dp[i][1] + dp[i][2]\n    dp[i + 1][5] = 24 * dp[i][5] + dp[i][2] + dp[i][3]\n    dp[i + 1][6] = 25 * dp[i][6] + dp[i][1] + dp[i][3]\n    dp[i + 1][7] = 24 * dp[i][7] + dp[i][2]\n    dp[i + 1][8] = 25 * dp[i][8] + dp[i][4] + dp[i][7]\n    dp[i + 1][9] = 25 * dp[i][9] + dp[i][4] + dp[i][5] + dp[i][6]\n    dp[i + 1][10] = 25 * dp[i][10] + dp[i][5] + dp[i][7]\n    dp[i + 1][11] = 26 * dp[i][11] + dp[i][8] + dp[i][9] + dp[i][10]\n    \'\'\'\n    def stringCount(self, n: int) -> int:\n        MOD = pow(10,9) + 7\n        A = [[23,0,0,0,0,0,0,0,0,0,0,0],\n             [1,24,0,0,0,0,0,0,0,0,0,0],\n             [1,0,23,0,0,0,0,0,0,0,0,0],\n             [1,0,0,24,0,0,0,0,0,0,0,0],\n             [0,1,1,0,24,0,0,0,0,0,0,0],\n             [0,0,1,1,0,24,0,0,0,0,0,0],\n             [0,1,0,1,0,0,25,0,0,0,0,0],\n             [0,0,1,0,0,0,0,24,0,0,0,0],\n             [0,0,0,0,1,0,0,1,25,0,0,0],\n             [0,0,0,0,1,1,1,0,0,25,0,0],\n             [0,0,0,0,0,1,0,1,0,0,25,0],\n             [0,0,0,0,0,0,0,0,1,1,1,26]]\n        temp = n\n        count = 0\n        while temp > 0:\n            count += 1\n            temp //= 2\n        B = [[1,0,0,0,0,0,0,0,0,0,0,0],\n             [0,1,0,0,0,0,0,0,0,0,0,0],\n             [0,0,1,0,0,0,0,0,0,0,0,0],\n             [0,0,0,1,0,0,0,0,0,0,0,0],\n             [0,0,0,0,1,0,0,0,0,0,0,0],\n             [0,0,0,0,0,1,0,0,0,0,0,0],\n             [0,0,0,0,0,0,1,0,0,0,0,0],\n             [0,0,0,0,0,0,0,1,0,0,0,0],\n             [0,0,0,0,0,0,0,0,1,0,0,0],\n             [0,0,0,0,0,0,0,0,0,1,0,0],\n             [0,0,0,0,0,0,0,0,0,0,1,0],\n             [0,0,0,0,0,0,0,0,0,0,0,1]]\n        for i in range(count):\n            if n & (1 << i): B = self.matrix_multiply(A,B,MOD)\n            A = self.matrix_multiply(A,A,MOD)\n        u = [[1],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0],[0]]\n        C = self.matrix_multiply(B, u, MOD)\n        return C[-1][0]\n    # @lc code=end\n\n\n```
['Python3']