Unique Substrings in Wraparound String

Med

#0454Time: O(N^3), where N is the length of the string `s`. The two nested loops give a factor of `O(N^2)`. Inside the loop, creating and hashing a substring of length `L` takes `O(L)` time. Since `L` can be up to `N`, the total time is `O(N^3)`.Space: O(N^3), where N is the length of `s`. In the worst case (e.g., `s` is `"abc..."`), the set would store `O(N^2)` unique substrings, and the total space required for these strings can be up to `O(N^3)`.1 company

Patterns

Dynamic Programming

Data structures

String

Companies

MAQ Software

Prompt

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 <= 10⁵
s consists of lowercase English letters.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves generating all possible substrings of the input string s. For each substring, we check if it is a valid 'wraparound' substring according to the problem definition. All unique valid substrings are stored in a HashSet to avoid duplicates. The final answer is the size of this set.

Algorithm

Initialize an empty HashSet<String> called uniqueSubstrings.
Iterate through the string s with an index i from 0 to s.length() - 1 to define the start of a substring.
Start a nested loop with index j from i to s.length() - 1.
In the inner loop, check if the character s.charAt(j) follows s.charAt(j-1) (for j > i).
If they are consecutive, the substring s.substring(i, j+1) is valid. Add it to uniqueSubstrings.
If they are not consecutive, break the inner loop, as any longer substring starting at i will also be invalid.
After the loops complete, return the size of uniqueSubstrings.

Walkthrough

The core idea is to systematically explore every substring of s. We can use nested loops where the outer loop selects a starting index i, and the inner loop extends the substring to the right as long as it remains valid. A substring is valid if its characters are consecutive in the alphabet (e.g., 'a' -> 'b', 'z' -> 'a').

If a substring is found to be valid, it's added to a HashSet<String>. The HashSet automatically handles uniqueness, ensuring that we don't count the same substring multiple times. Finally, the number of unique valid substrings is simply the size of the set.

This method is straightforward but computationally expensive due to the large number of substrings and the overhead of string operations and storage.

1import java.util.HashSet;2import java.util.Set;3 4class Solution {5    public int findSubstringInWraproundString(String s) {6        if (s == null || s.length() == 0) {7            return 0;8        }9        Set<String> uniqueSubstrings = new HashSet<>();10        for (int i = 0; i < s.length(); i++) {11            // Add single character substring12            uniqueSubstrings.add(s.substring(i, i + 1));13            for (int j = i + 1; j < s.length(); j++) {14                char prev = s.charAt(j - 1);15                char curr = s.charAt(j);16                // Check for wraparound consecutiveness17                if ((curr - prev + 26) % 26 == 1) {18                    uniqueSubstrings.add(s.substring(i, j + 1));19                } else {20                    break; // End of consecutive sequence21                }22            }23        }24        return uniqueSubstrings.size();25    }26}

Complexity

Time

O(N^3), where N is the length of the string `s`. The two nested loops give a factor of `O(N^2)`. Inside the loop, creating and hashing a substring of length `L` takes `O(L)` time. Since `L` can be up to `N`, the total time is `O(N^3)`.

Space

O(N^3), where N is the length of `s`. In the worst case (e.g., `s` is `"abc..."`), the set would store `O(N^2)` unique substrings, and the total space required for these strings can be up to `O(N^3)`.

Trade-offs

Pros

Simple to understand and implement.
Directly follows the problem statement by generating, validating, and counting unique substrings.

Cons

Highly inefficient. Time complexity is at least O(N^2) due to nested loops, and can be up to O(N^3) because of string manipulation (substring creation and hashing).
High space complexity, as the HashSet might need to store O(N^2) substrings, leading to O(N^3) space usage in the worst case.
Will result in a 'Time Limit Exceeded' (TLE) error for the given constraints (N <= 10^5).

This efficient approach avoids generating and storing all substrings. Instead, it leverages a key insight: if we have multiple valid substrings ending with the same character, say 'c', like "abc" and "bc", the shorter one ("bc") is always a suffix of the longer one ("abc"). Therefore, to count all unique substrings ending in 'c', we only need to find the length of the longest valid substring ending in 'c'. The total count is the sum of these maximum lengths for each character from 'a' to 'z'.

Algorithm

Create an integer array maxLength of size 26, initialized to zeros.
Initialize an integer currentLength = 0.
Iterate through the string s from i = 0 to s.length() - 1.
If i > 0 and s.charAt(i) is consecutive to s.charAt(i-1) (with wraparound), increment currentLength.
Otherwise, reset currentLength to 1.
Let index = s.charAt(i) - 'a'.
Update maxLength[index] with the maximum of its current value and currentLength: maxLength[index] = Math.max(maxLength[index], currentLength).
After the loop, initialize totalCount = 0.
Iterate through the maxLength array and add each element to totalCount.
Return totalCount.

Walkthrough

The main idea is that the number of unique valid substrings is the sum of the lengths of the longest valid substrings ending with each character. For example, if the longest valid substring ending in 'c' is "abc" (length 3), it implies the existence of "c", "bc", and "abc". Any other valid substring ending in 'c' found elsewhere must be shorter than or equal to "abc" and thus is already accounted for.

We use an array, maxLength of size 26, to keep track of the maximum length of a valid substring ending with each letter of the alphabet. We iterate through the input string s once, maintaining a currentLength which represents the length of the valid substring ending at the current position i.

If s[i] and s[i-1] are consecutive, we increment currentLength.
If they are not, the streak is broken, and we reset currentLength to 1.
At each step i, we update the maxLength for the character s[i]: maxLength[s[i] - 'a'] = Math.max(maxLength[s[i] - 'a'], currentLength).

After iterating through the entire string, we sum up all the values in the maxLength array to get the total count.

1class Solution {2    public int findSubstringInWraproundString(String s) {3        if (s == null || s.length() == 0) {4            return 0;5        }6 7        // maxLength[i] stores the length of the longest valid substring ending with character 'a' + i.8        int[] maxLength = new int[26];9        int currentLength = 0;10 11        for (int i = 0; i < s.length(); i++) {12            // Check if current character is consecutive to the previous one13            if (i > 0 && (s.charAt(i) - s.charAt(i - 1) + 26) % 26 == 1) {14                currentLength++;15            } else {16                currentLength = 1;17            }18            19            int index = s.charAt(i) - 'a';20            maxLength[index] = Math.max(maxLength[index], currentLength);21        }22 23        // The total number of unique substrings is the sum of the max lengths.24        int totalCount = 0;25        for (int length : maxLength) {26            totalCount += length;27        }28 29        return totalCount;30    }31}

Complexity

Time

O(N), where N is the length of the string `s`. We perform a single pass through the string, and all operations inside the loop are constant time. The final summation takes O(26), which is constant.

Space

O(1). We only use an auxiliary array of size 26, which is constant and does not depend on the input string's length.

Trade-offs

Pros

Extremely efficient with a linear time complexity.
Uses constant extra space, making it very memory-efficient.
Solves the problem with a single pass over the input string.

Cons

The logic might be less intuitive at first glance compared to the brute-force approach.

Solutions

Solution

1class Solution {2public3  int findSubstringInWraproundString(String p) {4    int[] dp = new int[26];5    int k = 0;6    for (int i = 0; i < p.length(); ++i) {7      char c = p.charAt(i);8      if (i > 0 && (c - p.charAt(i - 1) + 26) % 26 == 1) {9        ++k;10      } else {11        k = 1;12      }13      dp[c - 'a'] = Math.max(dp[c - 'a'], k);14    }15    int ans = 0;16    for (int v : dp) {17      ans += v;18    }19    return ans;20  }21}

1class Solution {2public:3  int findSubstringInWraproundString(string p) {4    vector<int> dp(26);5    int k = 0;6    for (int i = 0; i < p.size(); ++i) {7      char c = p[i];8      if (i && (c - p[i - 1] + 26) % 26 == 1)9        ++k;10      else11        k = 1;12      dp[c - 'a'] = max(dp[c - 'a'], k);13    }14    int ans = 0;15    for (int &v : dp)16      ans += v;17    return ans;18  }19};

1class Solution:2    def findSubstringInWraproundString(self, p: str) -> int: dp = [0] * 26 k = 0 for i, c in enumerate(p): if i and (ord(c) - ord(p[i - 1])) % 26 == 1: k += 1 else: k = 1 idx = ord(c) - ord('a') dp[idx] = max(dp[idx], k) return sum(dp)

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem