# DP Approach using O(n) time/space

• The String `s` is wraparound of alphabet a-z, therefor all the substring that are present in `s` are formed with consecutive characters and wraparound. Since there are only 26 characters included in this substring, we can separate different substrings using `ending character` and `length`.

So we can use an array to record the length of longest consecutive substring in string `p` ending in `a....z`. For each substring, all `suffix` of that string are unique substrings that are present in both `p` and `s`.

Here is the implementation:

``````public int findSubstringInWraproundString(String p) {
if(p==null || p.length()==0) return 0;
char[] pp=p.toCharArray();
int preChain=1;
int[] longest=new int[26];
longest[pp[0]-'a']=1;
for(int i=1;i<pp.length;i++){
if(pre(pp[i])==pp[i-1]) preChain++;
else preChain=1;
longest[pp[i]-'a']=Math.max(longest[pp[i]-'a'], preChain);
}
int res=0;
for(int l:longest) res+=l;
return res;
}

public char pre(char a){
int tmp=((a-'a')-1)%26;
if(tmp<0) tmp+=26;
return (char)(tmp+'a');
}
``````

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