Problem statement

https://leetcode.com/problems/unique-substrings-in-wraparound-string/

Solution

Let dp[i] be the maximum length of substring which end with letter number i. For example dp[3] = 5 means, that maximum length of substring ending with letter c is equal to 5, that is there exists substring yzabc, but not exists substring xyzabc. Then we traverse our string and if next symbol is equal to previous plus 1 (or z -> a), then we increase variable max_len: which denotes the maximum length of increasing substring, ending in given place. Also we update our dp table while we iterate. Also I use stop symbol in the end of string.

Complexity

Time complexity is O(n), space is O(26).

Code

class Solution:
    def findSubstringInWraproundString(self, p):
        dp, p, max_len = [0] * 26, p + "#", 1

        for i in range(1, len(p)):
            place = ord(p[i-1])%26
            dp[place] = max(max_len, dp[place])
            if (ord(p[i]) - ord(p[i-1])) % 26 == 1:
                max_len += 1
            else:       
                max_len = 1
                
        return sum(dp)