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())