Unique Substrings in Wraparound String

medium string dp

Problem

The wraparound string is the infinite string "abcdefghijklmnopqrstuvwxyzabcd...". Given a string s, return the number of unique non-empty substrings of s that appear as a contiguous substring of the wraparound string.

Inputs = "zab"

Output6

"z", "a", "b", "za", "ab", "zab" are all in the wraparound string.

def find_substring_in_wrapround_string(s):
    best = [0] * 26
    run = 0
    for i, ch in enumerate(s):
        if i > 0 and (ord(ch) - ord(s[i-1])) % 26 == 1:
            run += 1
        else:
            run = 1
        idx = ord(ch) - ord('a')
        best[idx] = max(best[idx], run)
    return sum(best)

function findSubstringInWraproundString(s) {
  const best = new Array(26).fill(0);
  let run = 0;
  for (let i = 0; i < s.length; i++) {
    if (i > 0 && ((s.charCodeAt(i) - s.charCodeAt(i - 1) + 26) % 26) === 1) {
      run++;
    } else {
      run = 1;
    }
    const idx = s.charCodeAt(i) - 97;
    best[idx] = Math.max(best[idx], run);
  }
  return best.reduce((a, b) => a + b, 0);
}

class Solution {
    public int findSubstringInWraproundString(String s) {
        int[] best = new int[26];
        int run = 0;
        for (int i = 0; i < s.length(); i++) {
            if (i > 0 && (s.charAt(i) - s.charAt(i - 1) + 26) % 26 == 1) run++;
            else run = 1;
            int idx = s.charAt(i) - 'a';
            best[idx] = Math.max(best[idx], run);
        }
        int sum = 0;
        for (int v : best) sum += v;
        return sum;
    }
}

int findSubstringInWraproundString(string s) {
    vector<int> best(26, 0);
    int run = 0;
    for (int i = 0; i < (int)s.size(); i++) {
        if (i > 0 && (s[i] - s[i-1] + 26) % 26 == 1) run++;
        else run = 1;
        int idx = s[i] - 'a';
        best[idx] = max(best[idx], run);
    }
    int sum = 0;
    for (int v : best) sum += v;
    return sum;
}

Explanation

The clever observation is that any valid substring (one that follows the alphabet, wrapping z → a) is fully determined by its last letter and its length. So instead of listing substrings, we record, for each ending letter, the longest valid run that ends there.

We scan s once, keeping a counter run. If the current letter follows the previous one in the alphabet — checked with (ord(ch) - ord(prev)) % 26 == 1 so that z→a counts — we extend the run. Otherwise we reset run to 1.

For the current letter we store best[idx] = max(best[idx], run). Why does this avoid double-counting? A run of length L ending at a letter contributes exactly L distinct substrings that end with that letter (lengths 1 through L). Keeping only the longest run per ending letter counts each unique substring once.

The answer is simply sum(best) across all 26 letters.

Example: s = "zab". The whole string is one valid run, giving runs of length 1 at z, 2 at a, 3 at b. Sum 1 + 2 + 3 = 6.

Time: O(n) Space: O(1) (26 letters)