Unique Substrings in Wraparound String
Intuition
Solution
class Solution:
def findSubstringInWraproundString(self, p: str) -> int:
next_c = {string.ascii_lowercase[i]: string.ascii_lowercase[(i + 1) % 26] for i in range(26)}
start = 0
prev = None
max_length = {c:0 for c in string.ascii_lowercase}
for index, c in enumerate(p):
if index == 0 or c != next_c[prev]:
length = 1
start = c
else:
length += 1
max_length[start] = max(max_length[start], length)
prev = c
for i in range(26 * 2):
c1 = string.ascii_lowercase[(i+1) % 26]
c2 = string.ascii_lowercase[i % 26]
max_length[c1] = max(
max_length[c1],
max_length[c2] - 1
)
return sum(max_length.values())