Unique Substrings In Wraparound String

To solve this coding challenge effectively, it involves a few detailed steps:
  1. Understand that the
    base
    string is an infinite concatenation of "abcdefghijklmnopqrstuvwxyz".
  2. The task is to find all the unique non-empty substrings of the input string
    s
    that can be found in the
    base
    string.
  3. A substring is valid if characters follow one another in the English alphabet circularly (i.e., 'z' followed by 'a' is valid).
  4. The solution involves dynamically storing the maximum length of the substring that ends at each character in an array
    dp
    .
  5. We iterate through the input string and update the
    dp
    array based on whether each character can follow the previous character in a wraparound manner.
  6. Finally, sum up all values in the
    dp
    array to get the total number of unique substrings.
  7. Explanation

    The solution utilizes a dynamic programming approach:
  8. Initialization :
    • Create an array
      dp
      of size 26 (one for each letter in the alphabet) initialized to zero. This array will store the maximum length of substrings ending with each character.
    • Set
      dp[ord(s[0]) - ord('a')]
      to 1 for the first character of the input string, treating it as a starting point of a valid substring.
  9. Iterate Through String :
    • Traverse the string starting from the second character.
    • For each character, check if it follows the previous character in the alphabet, considering wraparound (i.e., 'a' following 'z').
    • Update the length of the current valid substring if the condition is met, or reset it to 1 if not.
  10. Update Dynamic Array :
    • For every character, update the corresponding index in
      dp
      with the maximum length of the substring ending at that character.
  11. Sum the Results :
    • The sum of all values in
      dp
      gives the number of unique substrings because every increment in a position
      dp[i]
      represents a new unique substring.

Pseudocode

Here is the detailed pseudocode with comments explaining each step:
                                            
FUNCTION findSubstringInWraparoundString(s):
    # Check if the input string is empty
    IF s IS NULL OR LENGTH(s) == 0:
        RETURN 0
    
    # Initialize dp array with size 26 (for each letter in the alphabet)
    dp = ARRAY of SIZE 26 initialized to 0
    
    # Set the first character's position in dp to 1
    index = ASCII(s[0]) - ASCII('a')
    dp[index] = 1
    
    # Initialize the length of the current valid substring
    currentLength = 1
    
    # Loop through the string starting from the second character
    FOR i FROM 1 TO LENGTH(s) - 1:
        # Check if the current character follows the previous one in the wraparound manner
        IF ASCII(s[i]) - ASCII(s[i-1]) == 1 OR ASCII(s[i-1]) - ASCII(s[i]) == 25:
            # Increment the current valid substring length
            currentLength = currentLength + 1
        ELSE:
            # Reset the length as it's no longer valid in sequence
            currentLength = 1
        
        # Update the dp array with the maximum length of substring ending at this character
        index = ASCII(s[i]) - ASCII('a')
        dp[index] = MAX(dp[index], currentLength)
    
    # Sum up all values in the dp array to get the number of unique substrings
    uniqueSubstringsCount = SUM(dp)
    
    RETURN uniqueSubstringsCount