simple python O(1) space, O(n) time with explanation


  • 0
    J

    One key observation is that: a substring ending with char C with max length L will have L substrings. E.g. zabc, substring which ends with "c" will has max length 4, then it has zabc, abc, bc, c four cases which all end with "c". So the code need to remember the max length ending with 26 characters

    class Solution(object):
        def findSubstringInWraproundString(self, p):
            """
            :type p: str
            :rtype: int
            """
            dp = [0]*26
            l = 0
            cur = ""
            for c in p:
                index = ord(c) - ord("a")
                if not cur or ord(c) - ord(cur) == 1 or (c == "a" and cur == "z"):
                    l += 1
                else:
                    l = 1
                dp[index] = max(dp[index], l)
                cur = c
            
            return sum(dp)
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.