# Simple DP Python beats 90%, O(n) time, O(1) space

• Using a dictionary to store the highest value for each character from a to z, and we can handle the duplicate characters in p easily.

class Solution(object):
def findSubstringInWraproundString(self, p):
"""
:type p: str
:rtype: int
"""
values = collections.defaultdict(int)
last_c, last_v = "", 0
for c in p:
v = last_v + 1 if last_c and (ord(c) - ord(last_c)) % 26 == 1 else 1
values[c] = max(values[c], v)
last_c, last_v = c, v
return sum(values.values())

Evolved from 1 dimensional DP version as attached.

class Solution(object):
def findSubstringInWraproundString(self, p):
"""
:type p: str
:rtype: int
"""
mark = collections.defaultdict(int)
n = len(p)
dp = [0] * n
for i in range(n):
dp[i] = dp[i-1]+1 if i and (ord(p[i]) - ord(p[i-1])) % 26 == 1 else 1
mark[p[i]] = max(mark[p[i]], dp[i])
return sum(mark.values())

• Can skip the else part if dp is initialized as [1]*n.

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