467. Unique Substrings in Wraparound String

Time: O(n)

Space: O(1)

Intuition

Count unique substrings of p that are substrings of the infinite wraparound string "abcdefg...z abcdef...". A substring is valid if it's consecutive in wrap-around order.

Algorithm

1Track current run length of valid consecutive characters.
2For each character c, if p[i]-p[i-1]==1 or wraparound (za), extend run; else reset to 1.
3Track max run length ending at each character. Answer = sum of these maxes.

Example Walkthrough

Input: p="zab"

1.z: run=1, max[z]=1.
2.a: z→a is wraparound, run=2, max[a]=2.
3.b: a→b consecutive, run=3, max[b]=3.
4.Total=1+2+3=6.

Output: 6

Common Pitfalls

•Count by last character to avoid duplicates: each unique substring ending at character c of max length L contributes L unique substrings.

467.cs

// Approach: Track the longest consecutive run ending at each character;
// sum of per-character maximums is the total unique substring count.
// Time: O(n) Space: O(1)

public class Solution
{
    public int FindSubstringInWraproundString(string p)
    {
        int maxLength = 1;
        // count[i] := the number of substrings ending in ('a' + i)
        int[] count = new int[26];

        for (int i = 0; i < p.Length; ++i)
        {
            if (i > 0 && (p[i] - p[i - 1] == 1 || p[i - 1] - p[i] == 25))
                ++maxLength;
            else
                maxLength = 1;
            int index = p[i] - 'a';
            count[index] = Math.Max(count[index], maxLength);
        }

        return count.Sum();
    }
}

Was this solution helpful?