We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Unique Substrings in Wraparound String

Number: 467

Difficulty: Medium

Paid? No

Companies: Amazon, MAQ Software

Problem Description

Given a string s, count the number of unique non-empty substrings of s that are present in an infinite wraparound string of the alphabet ("...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd..."). A substring is considered to be present in the wraparound string if its characters appear consecutively as in the cyclic order of 'a' to 'z'.

Key Insights

  • A valid substring in the wraparound string consists of consecutive characters in alphabetical order (with wrap from 'z' to 'a').
  • For every character in s, determine the longest valid substring ending at that character.
  • Use an array (or map) to track for each letter the maximum length of a valid substring ending with that letter.
  • The total number of unique substrings ending with a specific letter is equal to the maximum length computed for that letter.
  • Summing all these maximum lengths gives the final result.

Space and Time Complexity

Time Complexity: O(n), where n is the length of s (each character is processed once).
Space Complexity: O(1), since the storage needed is constant (an array of size 26).

Solution

We use a dynamic programming approach where we iterate over the string s. During the iteration, we check if the current character is consecutive to the previous character (taking wraparound into account). If it is, we extend the length of the current valid substring; otherwise, we reset the length to 1.

For each character, update a count array of length 26 (one for each letter) to store the maximum valid substring length ending with that letter. This is because any valid substring ending with a character contributes all of its substrings (of lengths 1 through the maximum length) as unique substrings due to the properties of consecutive sequences. Finally, sum the count array values to get the total count of unique substrings.

Code Solutions

# Python solution with detailed comments

def findSubstringInWraproundString(s: str) -> int:
    # dp array holds the longest valid substring length ending with each letter
    dp = [0] * 26
    current_length = 0
    
    # Iterate over each character in the given string
    for i in range(len(s)):
        # Check if the current character is consecutive to the previous character in the wrap-around string
        if i > 0 and ((ord(s[i]) - ord(s[i-1]) == 1) or (s[i-1] == 'z' and s[i] == 'a')):
            current_length += 1
        else:
            current_length = 1
        
        # Map character to index in dp array (0 for 'a', 1 for 'b', etc.)
        index = ord(s[i]) - ord('a')
        # Update the dp value for the current character with the maximum length seen
        dp[index] = max(dp[index], current_length)
        
    # The result is the sum of dp array values, each dp[i] indicates unique substrings ending in that letter
    return sum(dp)

# Example usage:
s = "zab"
print(findSubstringInWraproundString(s))  # Expected output: 6
← Back to All Questions