algoadvance

We are given a string p consisting of lowercase English letters. Suppose we have a string ‘s’ that consists of the infinite wraparound string of “abcdefghijklmnopqrstuvwxyz”, so s looks like this: “…zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd…”.

We need to determine the number of unique non-empty substrings of p that are substrings of s.

Clarifying Questions

1. Length Constraints: What is the maximum length of string p?
   • The length of p can be up to 10,000.
2. Character Constraints: Are there any characters in p that are outside the range ‘a’ to ‘z’?
   • No, the string p consists only of lowercase English letters.
3. Output: Are we only interested in the count of unique substrings, or do we need to list them?
   • We only need the count of unique substrings.

Strategy

1. Wraparound Consideration:
   • The wraparound string “s” can be visualized as a sequence where ‘z’ is followed by ‘a’, forming a cycle.
2. Dynamic Programming Approach:
   • Use an array dp where dp[c] stores the maximum length of the substring ending with character c.
   • Traverse through the string p, for each character, update the lengths of substrings that fit the wraparound condition.
   • Maintain a count of the maximum length of valid substrings ending with each character from ‘a’ to ‘z’.
3. Length Update:
   • For each character in the string p, check if it is the next character in the wraparound sequence of the previous character.
   • If yes, increment the length of the substring; otherwise, reset it to 1.
   • Update the dp array with the maximum length found for each endpoint character.
4. Result Calculation:
   • The answer is the sum of all values in the dp array, giving the count of unique substrings.

Code

def findSubstringInWraproundString(p: str) -> int:
    if not p:
        return 0

    dp = {chr(i): 0 for i in range(ord('a'), ord('z') + 1)}
    max_len_current = 0
    
    for i in range(len(p)):
        if i > 0 and (ord(p[i]) - ord(p[i - 1]) == 1 or ord(p[i - 1]) - ord(p[i]) == 25):
            max_len_current += 1
        else:
            max_len_current = 1
        dp[p[i]] = max(dp[p[i]], max_len_current)
    
    return sum(dp.values())

# Example usage
p = "zab"
print(findSubstringInWraproundString(p))  # Output should be 6

Time Complexity

• Time Complexity: O(n), where n is the length of the string p. Each character of the string is processed exactly once.
• Space Complexity: O(1), because the dp array stores a fixed number of characters (26 letters in the alphabet), resulting in constant space usage.

This ensures an efficient calculation of the number of unique substrings that fit the given conditions.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?