Scale Engineer

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 <= 105
  • 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.

import java.util.HashSet;import java.util.Set; class Solution {    public int findSubstringInWraproundString(String s) {        if (s == null || s.length() == 0) {            return 0;        }        Set<String> uniqueSubstrings = new HashSet<>();        for (int i = 0; i < s.length(); i++) {            // Add single character substring            uniqueSubstrings.add(s.substring(i, i + 1));            for (int j = i + 1; j < s.length(); j++) {                char prev = s.charAt(j - 1);                char curr = s.charAt(j);                // Check for wraparound consecutiveness                if ((curr - prev + 26) % 26 == 1) {                    uniqueSubstrings.add(s.substring(i, j + 1));                } else {                    break; // End of consecutive sequence                }            }        }        return uniqueSubstrings.size();    }}

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).

Solutions

class Solution {public  int findSubstringInWraproundString(String p) {    int[] dp = new int[26];    int k = 0;    for (int i = 0; i < p.length(); ++i) {      char c = p.charAt(i);      if (i > 0 && (c - p.charAt(i - 1) + 26) % 26 == 1) {        ++k;      } else {        k = 1;      }      dp[c - 'a'] = Math.max(dp[c - 'a'], k);    }    int ans = 0;    for (int v : dp) {      ans += v;    }    return ans;  }}

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 →

Next problem