Unique Substrings in Wraparound String - Solution & Explanation
Problem Statement
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 <= 105sconsists of lowercase English letters.
Approach Overview
Problem Overview: Given a string p, count how many unique non‑empty substrings of p appear in the infinite wraparound string "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz...". The wraparound rule means 'z' is followed by 'a', so substrings like "zab" are valid sequences.
Approach 1: Dynamic Programming with Substring Tracking (O(n) time, O(1) space)
The key observation: if you know the longest valid wraparound substring ending at each character, you automatically know how many unique substrings end there. Maintain an array of size 26 where dp[c] stores the maximum length of a valid wraparound substring ending with character c. Iterate through p and extend the current sequence when consecutive characters follow the wraparound rule (p[i] - p[i-1] == 1 or 'z' → 'a'). Update dp for the current character with the maximum length seen. Summing all values in dp gives the total number of unique substrings. This works because shorter substrings ending at the same character are already included within the longest one.
This method avoids generating all substrings explicitly. Instead, it tracks only the longest valid chain for each character, keeping memory constant at 26 entries. The approach combines ideas from dynamic programming and string traversal.
Approach 2: Sliding Window Technique (O(n) time, O(1) space)
You can also view the problem as scanning contiguous segments that follow the wraparound order. Use a sliding window to track the current valid segment length while iterating through the string. When the wraparound condition breaks, reset the window length to 1. For each step, update the best length seen for the current ending character, similar to the DP array in the previous method. This approach emphasizes sequential scanning and window expansion while still storing only 26 character states.
The sliding window interpretation is often easier to reason about during implementation because you directly track the length of the current valid substring segment. It still relies on the same counting principle: the longest substring ending at a character determines how many unique substrings end there.
Recommended for interviews: The dynamic programming approach with substring tracking is the expected solution. It demonstrates that you recognized the wraparound property and avoided brute‑force substring generation. Interviewers want to see the insight that only the longest valid substring ending at each character matters. Explaining why the dp[26] array prevents duplicates shows strong understanding of both dynamic programming and substring counting patterns in string problems.
Approach 1: Dynamic Programming with Substring Tracking
In this approach, we use dynamic programming to keep track of the maximum length of valid continuous substrings ending with each character. We maintain an array, dp, where dp[i] represents the maximum length of a valid substring ending with the character corresponding to the position i in the alphabet.
We iterate through the string s and at each step, determine if the current character can be attached to the previous character to extend a valid substring within the wraparound string. If it can, we increment the count; otherwise, we start a new substring.
At the end of the loop, the sum of values in dp gives us the number of unique substrings as each entry in dp represents the maximum possible unique substrings for a given character as the last.
This C implementation uses an array dp of size 26 to track the longest substring ending with each letter. We iterate over string p and update dp based on whether the current character continues a valid substring.
Complexity
Time Complexity: O(n) where n is the length of the string p.
Space Complexity: O(1) since the dp array size is constant at 26.
Approach 2: Sliding Window Technique
This approach involves optimizing the problem by using a sliding window to track the continuous substrings directly. The window is expanded outwards whenever a valid extension (either a subsequent alphabetic character or wrap from 'z' to 'a') is found and contracted whenever the sequence breaks.
We populate a set to store potentially valid substrings and then count them based on unique entries. However, this technique is often less efficient compared to DP-based approaches due to repeated set operations.
This implementation makes use of a sliding window approach to track the start and end of 'valid' substrings, employing a set to automatically filter duplicates.
Code
Python
JavaScript
Complexity
Time Complexity: Generally O(n^2) in the worst case because of the add operation inside the window sliding loop.
Space Complexity: Potentially O(n^2) in the worst case if all substrings are unique.
Approach 3: Dynamic Programming
We can define an array f of length 26, where f[i] represents the length of the longest consecutive substring ending with the ith character. The answer is the sum of all elements in f.
We define a variable k to represent the length of the longest consecutive substring ending with the current character. We iterate through the string s. For each character c, if the difference between c and the previous character s[i - 1] is 1, then we increment k by 1, otherwise, we reset k to 1. Then we update f[c] to be the larger value of f[c] and k.
Finally, we return the sum of all elements in f.
The time complexity is O(n), where n is the length of the string s. The space complexity is O(|\Sigma|), where \Sigma is the character set, in this case, the set of lowercase letters.
Complexity Comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming with Substring Tracking | Time Complexity: O(n) where n is the length of the string |
| Sliding Window Technique | Time Complexity: Generally O(n^2) in the worst case because of the add operation inside the window sliding loop. |
| Dynamic Programming | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming with Substring Tracking | O(n) | O(1) | Optimal approach. Best for interviews and large inputs since it tracks only the longest valid substring per character. |
| Sliding Window Technique | O(n) | O(1) | Useful when reasoning about contiguous valid segments while scanning the string sequentially. |
Video Solution
Leetcode 467. Unique Substrings in Wraparound String • Elite Code • 1,821 views views
Watch 7 more video solutions →Frequently Asked Questions
Is Unique Substrings in Wraparound String easy or hard?
Unique Substrings in Wraparound String Python/Java solution
How to solve Unique Substrings in Wraparound String in O(n)?
What is the best approach for Unique Substrings in Wraparound String?
Is Unique Substrings in Wraparound String asked at Google/Amazon/Meta?
What data structure is used in Unique Substrings in Wraparound String?
What is the time complexity of Unique Substrings in Wraparound String?
Ready to solve this problem?
Practice Unique Substrings in Wraparound String with our built-in code editor and test cases.
Practice on FleetCode