DP Approach using O(n) time/space


  • 0

    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');
        }
    

Log in to reply
 

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