# Unique Substrings in Wraparound String
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/unique-substrings-in-wraparound-string)
Canonical: https://scaleengineer.com/dsa/problems/unique-substrings-in-wraparound-string
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** String
**Companies:** [MAQ Software](https://scaleengineer.com/companies/maq-software)
---
## Problem
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
## Brute Force using a Set
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.
**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)`.
**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`).
### Explanation
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.

```java
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();
    }
}
```
### 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`.

## Dynamic Programming with Constant Space
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'.
**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.
**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.
### Explanation
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.

```java
class Solution {
    public int findSubstringInWraproundString(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }

        // maxLength[i] stores the length of the longest valid substring ending with character 'a' + i.
        int[] maxLength = new int[26];
        int currentLength = 0;

        for (int i = 0; i < s.length(); i++) {
            // Check if current character is consecutive to the previous one
            if (i > 0 && (s.charAt(i) - s.charAt(i - 1) + 26) % 26 == 1) {
                currentLength++;
            } else {
                currentLength = 1;
            }
            
            int index = s.charAt(i) - 'a';
            maxLength[index] = Math.max(maxLength[index], currentLength);
        }

        // The total number of unique substrings is the sum of the max lengths.
        int totalCount = 0;
        for (int length : maxLength) {
            totalCount += length;
        }

        return totalCount;
    }
}
```
### 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`.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

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

```

### Python

```python
class Solution:
    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)

```