Problem Description
Given a string s, return the number of unique non-empty substrings of s that are present in the infinite wraparound string of "abcdefghijklmnopqrstuvwxyz".
Key Insights
- The wraparound string allows for continuous substrings that can wrap from 'z' to 'a'.
- Consecutive characters in the string s that follow this wraparound pattern can form valid substrings.
- Unique substrings can be counted based on the lengths of segments of valid consecutive characters.
Space and Time Complexity
Time Complexity: O(n)
Space Complexity: O(1)
Solution
To solve the problem, we can iterate through the string s and identify segments of consecutive characters that fit within the wraparound string pattern. For each character, we can check if it follows the previous character based on the wraparound condition (i.e., the next character should be either the same or the next in the alphabet, with 'a' following 'z'). We maintain a count of the length of these segments and use it to determine the number of unique substrings that can be formed from them.
We will utilize a simple loop to traverse the string while keeping track of the current segment length. The number of unique substrings that can be formed from a segment of length L is given by the formula L * (L + 1) / 2, since every substring of length 1 to L can be formed.