Skip to content

Unique Substrings in Wraparound String⚓︎

Link

Description⚓︎

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:

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⚓︎

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    int findSubstringInWraproundString(string s) {
        int n = s.length();
        vector<int> str(n);
        for (int i = 0; i < n; i++) {
            str[i] = s[i] - 'a';
        }

        array<int, 26> dp{};
        dp[str[0]] = 1;

        int len = 1;
        for (int i = 1; i < n; i++) {
            int curr = str[i], prev = str[i - 1];
            if ((prev == 25 && curr == 0) || prev + 1 == curr) {
                len++;
            } else {
                len = 1;
            }
            dp[curr] = max(dp[curr], len);
        }

        return accumulate(dp.begin(), dp.end(), 0);
    }
};

Another way of writing:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int findSubstringInWraproundString(string s) {
        array<int, 26> dp{};
        int len = 0;

        for (int i = 0; i < s.length(); 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);
        }

        return accumulate(dp.begin(), dp.end(), 0);
    }
};
  • Time complexity: \(O(n)\);
  • Space complexity: \(O(26)\).