Leetcode Unique Substrings in Wraparound String problem solution

In this Leetcode Unique Substrings in Wraparound String problem solution We define the string s to be the infinite wraparound string of “abcdefghijklmnopqrstuvwxyz”, so s will look like this:

“…zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd….”.

Given a string p, return the number of unique non-empty substrings of p are present in s.

Leetcode Unique Substrings in Wraparound String problem solution

Topics we are covering

Problem solution in Python.

def findSubstringInWraproundString(self, p: str) -> int:
        d={x:1 for x in p}
        cur=1
        for x in range(len(p)-1,-1,-1):
            if x==len(p)-1 or (ord(p[x+1])-ord(p[x]))%26!=1:
                cur=1
            else:
                cur+=1
                d[p[x]]=max(d[p[x]],cur)
        return sum(d.values())

Problem solution in Java.

class Solution {
    public int findSubstringInWraproundString(String p) {
        if(p.length()==0)return 0;
        int res=0;
        int table[]=new int[26];
        int dp[]=new int[p.length()];
        dp[0]=1;
        table[p.charAt(0)-'a']=1;
        for(int i=1;i<p.length();i++){
            char cur=p.charAt(i);
            char pre=p.charAt(i-1);
            if(cur-pre==1||(cur=='a'&&pre=='z')){
                dp[i]=dp[i-1]+1;
            }else{
                dp[i]=1;
            }
            table[cur-'a']=Math.max(table[cur-'a'],dp[i]);
        }
        for(int i : table)res+=i;
        return res;
    }
}

Problem solution in C++.

int findSubstringInWraproundString(string p) {
        int n=p.size(),ans=1,dp=1;
        vector<int> maxFound(26,0);
        maxFound[p[0]-'a']=1;
        for(int i=1;i<n;i++){
            if((p[i-1]-'a'+1)%26!=p[i]-'a'){
                dp=1;
            }else{
                dp++;
            }
            ans+=max(0,dp-maxFound[p[i]-'a']);
            maxFound[p[i]-'a']=max(maxFound[p[i]-'a'],dp);
        }
        return ans;
    }

coding problems solutions