Unique Substrings In Wraparound String - Leetcode Solution

Problem statement:

Consider the string s to be the infinite wraparound string of "abcdefghijklmnopqrstuvwxyz", so s will look like this: "...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd....".

Now we have another string p. Your task is to find out how many unique non-empty substrings of p are present in s. In particular, your output should be a single integer which equals to the number of distinct substrings of p in s.

Solution:

To solve this problem, we need to first understand that the given string s is actually an infinite string that wraps around itself. This means that if we take any substring of s, it can be wrapped around to form another substring.

Let's take an example to illustrate this. Suppose p="abc". Now all the substrings of p that can be formed are "a", "ab", "abc", "b", "bc" and "c". Now if we look at s, we can see that "a" and "abc" are present as substrings. But what about "ab" and "bc"? These two substrings are not present in s as they cannot be formed by wrapping around any substring of s.

Based on this observation, we can conclude that the only substrings of p that will be present in s are those that are formed by the longest continuous block of characters in p that are present in s.

For example, if p="abcdb", the longest block of characters that are present in s is "abcd" and therefore the only substrings of p that will be present in s are "abcd" and "ab".

To find the answer to this problem, we can use dynamic programming. We can create an array dp where dp[i] represents the length of the longest block of characters that ends at the i-th character of p and is present in s.

Initially, dp[0]=1 as the first character of p is always present in s. Then for each i from 1 to n-1, where n is the length of p, we can check if the i-th character of p can be added to the longest block of characters that ends at the i-1-th character and is present in s. If it can, we add 1 to dp[i]. Otherwise, dp[i]=1.

After finding dp, we can simply sum up all its elements to get the number of unique non-empty substrings of p that are present in s.

Here is the Python code for the same:

def findSubstringInWraproundString(p):

#create dp array
dp = [1]*len(p)

#check for each character
for i in range(1,len(p)):

    #if it can be added to the longest block of characters that ends at
    #the i-1th position, add 1 to dp[i]
    if (ord(p[i])-ord(p[i-1]))%26 == 1:
        dp[i] = dp[i-1]+1

#store the count of unique non-empty substrings of p that are present in s
count = 0

#sum up the elements of dp
for i in range(len(dp)):
    count += dp[i]

return count

Time complexity: O(n) where n is the length of p.

Space complexity: O(n) as we are creating an array of size n.

1