{x}
blog image

Unique Substrings in Wraparound String

We define the string base to be the infinite wraparound string of "abcdefghijklmnopqrstuvwxyz", so base will look like this:

  • "...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd....".

Given a string s, return the number of unique non-empty substrings of s are present in base.

 

Example 1:

Input: s = "a"
Output: 1
Explanation: Only the substring "a" of s is in base.

Example 2:

Input: s = "cac"
Output: 2
Explanation: There are two substrings ("a", "c") of s in base.

Example 3:

Input: s = "zab"
Output: 6
Explanation: There are six substrings ("z", "a", "b", "za", "ab", and "zab") of s in base.

 

Constraints:

  • 1 <= s.length <= 105
  • s consists of lowercase English letters.

Solution Explanation: Unique Substrings in Wraparound String

This problem asks to find the number of unique non-empty substrings of a given string s that are present in the infinite wraparound string "abcdefghijklmnopqrstuvwxyz...". A naive approach would involve generating all substrings and checking if each is a substring of the wraparound string, leading to high time complexity. A more efficient dynamic programming approach is used here.

Approach: Dynamic Programming

The solution leverages dynamic programming to avoid redundant calculations. It utilizes an array f of size 26 (one for each lowercase letter), where f[i] stores the maximum length of a substring ending with the i-th letter (considering the wraparound).

  1. Initialization: f is initialized with all zeros.

  2. Iteration: The code iterates through the input string s. For each character c:

    • It checks if this character forms a consecutive sequence with the previous character (considering the wraparound: 'z' followed by 'a' is considered consecutive).
    • If consecutive, a counter k (representing the length of the current consecutive substring) is incremented. Otherwise, k is reset to 1.
    • f[c] is updated to the maximum of its current value and k, ensuring we only track the maximum length of a consecutive substring ending with c.

  3. Result: Finally, the sum of all elements in f is returned. This sum represents the total number of unique substrings.

Time and Space Complexity Analysis

  • Time Complexity: O(n), where n is the length of the input string s. The code iterates through the string once.

  • Space Complexity: O(1). The space used by the f array is constant (26 elements), regardless of the input string size. Note that even though some implementations (like Python's) use a dictionary (hashmap), the space used by that dictionary is also bounded by a constant (26) in this case.

Code Implementation Details (Python Example)

from collections import defaultdict
 
class Solution:
    def findSubstringInWraproundString(self, s: str) -> int:
        f = defaultdict(int)  # Use defaultdict for easy handling of missing keys
        k = 0
        for i, c in enumerate(s):
            if i > 0 and (ord(c) - ord(s[i - 1])) % 26 == 1:  # Check for consecutive sequence (wraparound considered)
                k += 1
            else:
                k = 1
            f[c] = max(f[c], k)  # Update f[c] with the maximum length of a substring ending in c
        return sum(f.values())  # Return the sum of all lengths in f

The other language implementations follow the same algorithm, with minor syntax differences to handle array indexing, string manipulation, and maximum/sum calculations in their respective languages. The core logic remains consistent across all implementations.