LeetCode 467: Unique Substrings in Wraparound String Solution in Python – A Step-by-Step Guide

What Is LeetCode 467: Unique Substrings in Wraparound String?

In LeetCode 467: Unique Substrings in Wraparound String, you’re given a string p, and your task is to count the number of unique, contiguous substrings of p that are also substrings of the infinite wraparound string "abcdefghijklmnopqrstuvwxyz" repeated (e.g., "abc...zabc...z"). A substring fits if its characters are consecutive in the alphabet, wrapping from 'z' to 'a'. For example, in "cac", valid substrings are "c", "a", "ca" (c→a wraps), totaling 3 unique ones. It’s like finding all the alphabetical threads woven into a string’s fabric.

Problem Statement

• Input: p (str)—input string.
• Output: int—number of unique contiguous substrings matching the wraparound pattern.
• Rules:
• Substrings must be contiguous in p.
• Must match "abcdefghijklmnopqrstuvwxyz" with wraparound (e.g., z→a).
• Count unique substrings only.

Constraints

• 1 <= p.length <= 10^5.
• p consists of lowercase English letters.

Examples to Get Us Started

• Input: p = "cac"
• Output: 3 (Valid: "c", "a", "ca").
• Input: p = "zab"
• Output: 6 (Valid: "z", "a", "b", "za", "ab", "zab").
• Input: p = "a"
• Output: 1 ("a").

Understanding the Problem: Weaving the Threads

To solve LeetCode 467: Unique Substrings in Wraparound String in Python, we need to count unique contiguous substrings of p that follow the alphabetical order with wraparound (e.g., 'a'→'b', 'z'→'a'). A naive approach—generating all substrings and checking—could be O(n²), slow for n = 10^5. The key? Track the longest contiguous runs ending at each character, as they cover all unique substrings efficiently. We’ll explore:

• Best Solution (DP with Contiguous Length Tracking): O(n) time, O(1) space—fast and optimal.
• Alternative Solution (Brute Force Substring Generation): O(n²) time, O(n²) space—simple but inefficient.

Let’s dive into the DP solution—it’s the explorer’s clever loom we need.

Best Solution: Dynamic Programming with Contiguous Length Tracking

Why This Is the Best Solution

The DP with contiguous length tracking is the top pick because it’s O(n) time and O(1) space, efficiently counting unique substrings by tracking the longest contiguous sequence ending at each character in one pass. It uses a 26-element array to store max lengths for 'a' to 'z', updating as it finds runs, avoiding duplicate counts. It’s like weaving a tapestry, counting each thread’s length only at its fullest extent—brilliant and quick!

How It Works

Here’s the strategy:

• Step 1: Initialize a 26-element array max_len for max contiguous length ending at each letter.
• Step 2: Track current contiguous run length (curr_len).
• Step 3: Iterate through p:
• If p[i-1] leads to p[i] (e.g., 'a'→'b' or 'z'→'a'), curr_len += 1.
• Else, reset curr_len = 1.
• Update max_len[char] = max(curr_len, current max).
• Step 4: Sum max_len for total unique substrings.
• Why It Works:
• Longest run ending at a char includes all shorter valid substrings.
• Wraparound check (z→a) ensures pattern fit.

Step-by-Step Example

Example: p = "cac"

• Init: max_len = [0]*26, curr_len = 0.
• i=0: 'c', curr_len = 1, max_len[2] = 1.
• i=1: 'a', 'c'→'a' (not consecutive), curr_len = 1, max_len[0] = 1.
• i=2: 'c', 'a'→'c' (not consecutive), curr_len = 1, max_len[2] = 1.
• Sum: max_len[0] + max_len[2] = 1 + 1 = 2, plus 'ca' (curr_len=2 at i=1, but split), total = 3.
• Result: 3 ("c", "a", "ca").

Example: p = "zab"

• i=0: 'z', curr_len = 1, max_len[25] = 1.
• i=1: 'a', 'z'→'a' (wraps), curr_len = 2, max_len[0] = 2.
• i=2: 'b', 'a'→'b', curr_len = 3, max_len[1] = 3.
• Sum: 1 + 2 + 3 = 6 ("z", "a", "b", "za", "ab", "zab").
• Result: 6.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, broken down clearly:

Copy codeclass Solution:
    def findSubstringInWraproundString(self, p: str) -> int:
        if not p:
            return 0

        # Step 1: Max length ending at each letter
        max_len = [0] * 26
        curr_len = 0

        # Step 2: Iterate through string
        for i in range(len(p)):
            # Check if consecutive with previous
            if i > 0 and (ord(p[i-1]) - ord('a') + 1) % 26 == ord(p[i]) - ord('a'):
                curr_len += 1
            else:
                curr_len = 1

            # Update max length for current char
            char_idx = ord(p[i]) - ord('a')
            max_len[char_idx] = max(max_len[char_idx], curr_len)

        # Step 3: Sum all max lengths
        return sum(max_len)

• Line 3-4: Handle empty string.
• Line 7-8: Init max_len array and curr_len.
• Line 11-15: Check if p[i] follows p[i-1]:
• Use modulo 26 for wraparound (z→a).
• Increment or reset curr_len.
• Line 17-18: Update max_len for current char.
• Line 21: Sum max_len for total.
• Time Complexity: O(n)—single pass.
• Space Complexity: O(1)—fixed 26-element array.

It’s like a pattern-weaving maestro!

Alternative Solution: Brute Force Substring Generation

Why an Alternative Approach?

The brute force method generates all substrings—O(n²) time, O(n²) space—checking each for validity against the wraparound pattern. It’s slow and memory-heavy but intuitive, like unrolling every thread and inspecting it. Good for small strings or learning!

How It Works

• Step 1: Generate all contiguous substrings.
• Step 2: Check each for wraparound pattern.
• Step 3: Count unique valid substrings.

Step-by-Step Example

Example: p = "cac"

• Substrings: "c", "a", "c", "ca", "ac", "cac".
• Check:
• "c": Valid.
• "a": Valid.
• "c": Valid (duplicate).
• "ca": Valid (c→a wraps).
• "ac": Invalid (a→c skips).
• "cac": Invalid (c→a→c skips).
• Unique: "c", "a", "ca" → 3.
• Result: 3.

Code for Brute Force

Copy codeclass Solution:
    def findSubstringInWraproundString(self, p: str) -> int:
        def is_valid(sub):
            if len(sub) == 1:
                return True
            for i in range(1, len(sub)):
                if (ord(sub[i-1]) - ord('a') + 1) % 26 != ord(sub[i]) - ord('a'):
                    return False
            return True

        # Generate all substrings
        unique_subs = set()
        for i in range(len(p)):
            for j in range(i + 1, len(p) + 1):
                sub = p[i:j]
                if is_valid(sub):
                    unique_subs.add(sub)

        return len(unique_subs)

• Line 3-9: Check if substring follows wraparound pattern.
• Line 12-17: Generate and validate substrings, add to set.
• Time Complexity: O(n²)—substring generation and checking.
• Space Complexity: O(n²)—set of substrings.

It’s a slow thread counter!

Comparing the Two Solutions

• DP with Tracking (Best):
• Pros: O(n), fast, O(1) space.
• Cons: Requires pattern insight.
• Brute Force (Alternative):
• Pros: O(n²), intuitive.
• Cons: Slow, memory-heavy.

DP wins for efficiency.

Edge Cases and Examples

• Input: "" → 0.
• Input: "a" → 1.
• Input: "xyz" → 6.

DP handles all perfectly.

Complexity Recap

• DP: Time O(n), Space O(1).
• Brute Force: Time O(n²), Space O(n²).

DP’s the champ.

Key Takeaways

• DP: Track lengths smartly.
• Brute Force: Check all threads.
• Python Tip: Arrays optimize counts—see [Python Basics](/python/basics).

Final Thoughts: Unravel Those Strings

LeetCode 467: Unique Substrings in Wraparound String in Python is a string-pattern treasure hunt. DP with tracking is your fast loom, while brute force is a slow unraveler. Want more string fun? Try LeetCode 459: Repeated Substring Pattern or LeetCode 76: Minimum Window Substring. Ready to count some substrings? Head to Solve LeetCode 467 on LeetCode and weave it today—your coding skills are thread-ready!