Watch 9 video solutions for Unique Substrings in Wraparound String, a medium level problem involving String, Dynamic Programming. This walkthrough by Elite Code has 1,752 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 105s consists of lowercase English letters.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 | 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. |