forked from keon/algorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathk_factor.py
More file actions
87 lines (72 loc) · 2.44 KB
/
k_factor.py
File metadata and controls
87 lines (72 loc) · 2.44 KB
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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
"""
K-Factor of a String
The K factor of a string is the number of times 'abba' appears as a
substring. Given a length and a k_factor, count the number of strings of
that length whose K factor equals k_factor.
Reference: https://en.wikipedia.org/wiki/Dynamic_programming
Complexity:
Time: O(length^2)
Space: O(length^2)
"""
from __future__ import annotations
def find_k_factor(length: int, k_factor: int) -> int:
"""Count strings of given length with exactly k_factor 'abba' substrings.
Args:
length: Length of the strings to consider.
k_factor: Required number of 'abba' substrings.
Returns:
Number of strings satisfying the K-factor constraint.
Examples:
>>> find_k_factor(4, 1)
1
>>> find_k_factor(7, 1)
70302
"""
mat = [
[[0 for i in range(4)] for j in range((length - 1) // 3 + 2)]
for k in range(length + 1)
]
if 3 * k_factor + 1 > length:
return 0
mat[1][0][0] = 1
mat[1][0][1] = 0
mat[1][0][2] = 0
mat[1][0][3] = 25
for i in range(2, length + 1):
for j in range((length - 1) // 3 + 2):
if j == 0:
mat[i][j][0] = mat[i - 1][j][0] + mat[i - 1][j][1] + mat[i - 1][j][3]
mat[i][j][1] = mat[i - 1][j][0]
mat[i][j][2] = mat[i - 1][j][1]
mat[i][j][3] = (
mat[i - 1][j][0] * 24
+ mat[i - 1][j][1] * 24
+ mat[i - 1][j][2] * 25
+ mat[i - 1][j][3] * 25
)
elif 3 * j + 1 < i:
mat[i][j][0] = (
mat[i - 1][j][0]
+ mat[i - 1][j][1]
+ mat[i - 1][j][3]
+ mat[i - 1][j - 1][2]
)
mat[i][j][1] = mat[i - 1][j][0]
mat[i][j][2] = mat[i - 1][j][1]
mat[i][j][3] = (
mat[i - 1][j][0] * 24
+ mat[i - 1][j][1] * 24
+ mat[i - 1][j][2] * 25
+ mat[i - 1][j][3] * 25
)
elif 3 * j + 1 == i:
mat[i][j][0] = 1
mat[i][j][1] = 0
mat[i][j][2] = 0
mat[i][j][3] = 0
else:
mat[i][j][0] = 0
mat[i][j][1] = 0
mat[i][j][2] = 0
mat[i][j][3] = 0
return sum(mat[length][k_factor])