Sliding window problem with DP. Concise and easy to understand.


  • 0
    M

    The problem can basically look at this way. Find the max consecutive chars
    for every starting char.
    For instance, "abcd" is a substring with length 4 for point 'a', length 3 for point 'b', length 2 for point 'c' and length 1 for point 'd'.
    "abcdeabcd" will be length 5 for point 'a' since "abcde" is a longer sequence than "abcd". Then when we encounter a longer sequence than before, we simply update the difference and add to the totalCount. Here I use sliding window to solve the problem. Hope this will help.

        public int findSubstringInWraproundString(String p) {
            char[] arr=p.toCharArray();
            int[] start=new int[26];
            int count=0,left=0,right=1;
            
            while(right<=arr.length){
                while(right<arr.length&&((arr[right]==arr[right-1]+1)||(arr[right]=='a'&&arr[right-1]=='z'))){
                    right++;
                }
                
                while(left<right){
                    if(start[arr[left]-'a']<right-left){
                        count+=(right-left-start[arr[left]-'a']);
                        start[arr[left]-'a']=right-left;
                    }
                    left++;
                }
                right++;
            }
            return count;
            
        }
    

Log in to reply
 

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