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.

Examples

Example 1

1
2
3

Input: s = "a"
Output: 1
Explanation: Only the substring "a" of s is in base.

Example 2

1
2
3

Input: s = "cac"
Output: 2
Explanation: There are two substrings ("a", "c") of s in base.

Example 3

1
2
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^5
  • s consists of lowercase English letters.

Solution

Method 1 – Dynamic Programming (Track Max Length Ending at Each Character)

Intuition

For each character, track the maximum length of a valid substring ending with that character. The sum of these maximum lengths gives the number of unique substrings in the wraparound string.

Approach

  1. Initialize an array dp[26] to store the max length of valid substring ending with each character.
  2. Iterate through s, for each character:
    • If it continues a valid sequence (previous char is consecutive in wraparound), increment current length.
    • Otherwise, reset current length to 1.
    • Update dp for the current character with the max of current length and previous value.
  3. The answer is the sum of all values in dp.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

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

func findSubstringInWraproundString(s string) int {
    dp := make([]int, 26)
    len := 0
    for i := 0; i < len(s); i++ {
        if i > 0 && (int(s[i])-int(s[i-1])+26)%26 == 1 {
            len++
        } else {
            len = 1
        }
        idx := int(s[i] - 'a')
        if len > dp[idx] {
            dp[idx] = len
        }
    }
    ans := 0
    for _, x := range dp {
        ans += x
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    public int findSubstringInWraproundString(String s) {
        int[] dp = new int[26];
        int len = 0;
        for (int i = 0; i < s.length(); ++i) {
            if (i > 0 && (s.charAt(i)-s.charAt(i-1)+26)%26 == 1) len++;
            else len = 1;
            dp[s.charAt(i)-'a'] = Math.max(dp[s.charAt(i)-'a'], len);
        }
        int ans = 0;
        for (int x : dp) ans += x;
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    fun findSubstringInWraproundString(s: String): Int {
        val dp = IntArray(26)
        var len = 0
        for (i in s.indices) {
            if (i > 0 && (s[i]-s[i-1]+26)%26 == 1) len++
            else len = 1
            dp[s[i]-'a'] = maxOf(dp[s[i]-'a'], len)
        }
        return dp.sum()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def findSubstringInWraproundString(self, s: str) -> int:
        dp = [0] * 26
        l = 0
        for i, c in enumerate(s):
            if i > 0 and (ord(c) - ord(s[i-1]) + 26) % 26 == 1:
                l += 1
            else:
                l = 1
            idx = ord(c) - ord('a')
            dp[idx] = max(dp[idx], l)
        return sum(dp)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

impl Solution {
    pub fn find_substring_in_wrapround_string(s: String) -> i32 {
        let mut dp = vec![0; 26];
        let mut len = 0;
        let s = s.as_bytes();
        for i in 0..s.len() {
            if i > 0 && (s[i] + 26 - s[i-1]) % 26 == 1 {
                len += 1;
            } else {
                len = 1;
            }
            let idx = (s[i] - b'a') as usize;
            dp[idx] = dp[idx].max(len);
        }
        dp.iter().sum()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    findSubstringInWraproundString(s: string): number {
        const dp = Array(26).fill(0)
        let len = 0
        for (let i = 0; i < s.length; ++i) {
            if (i > 0 && (s.charCodeAt(i) - s.charCodeAt(i-1) + 26) % 26 === 1) len++
            else len = 1
            const idx = s.charCodeAt(i) - 97
            dp[idx] = Math.max(dp[idx], len)
        }
        return dp.reduce((a, b) => a + b, 0)
    }
}

Complexity

  • ⏰ Time complexity: O(n) — Single pass through s.
  • 🧺 Space complexity: O(1) — Only 26-element array for dp.