Unique Substrings In Wraparound String
To solve this coding challenge effectively, it involves a few detailed steps:
-
Understand that the
base
-
The task is to find all the unique non-empty substrings of the input string
s
base
- A substring is valid if characters follow one another in the English alphabet circularly (i.e., 'z' followed by 'a' is valid).
-
The solution involves dynamically storing the maximum length of the substring that ends at each character in an array
dp
-
We iterate through the input string and update the
dp
-
Finally, sum up all values in the
dp
- Initialization :
-
Create an array
dp
-
Set
dp[ord(s[0]) - ord('a')]
- 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.
- Update Dynamic Array :
-
For every character, update the corresponding index in
dp
- Sum the Results :
-
The sum of all values in
dp
dp[i]
Explanation
The solution utilizes a dynamic programming approach: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