# Solving Leetcode Interviews in Seconds with AI: Unique Substrings in Wraparound String


	# Introduction
	In this blog post, we will explore how to solve the LeetCode problem "467" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like [Chatmagic](https://www.chatmagic.app), we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

	# Problem Statement
	> 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:  Input: s = "a" Output: 1 Explanation: Only the substring "a" of s is in base.  Example 2:  Input: s = "cac" Output: 2 Explanation: There are two substrings ("a", "c") of s in base.  Example 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 <= 105 s consists of lowercase English letters.  

	# Explanation
	Here's the approach, complexity analysis, and Python code:

*   **Identify Relevant Substrings:** The crucial idea is that for each position in the input string `s`, we only need to consider the longest substring ending at that position that is a substring of the infinite base string.
*   **Dynamic Programming (Implicit):** We'll iterate through the string, maintaining a `max_len` array (or dictionary to be memory-efficient) that tracks the maximum length of a substring ending at each character 'a' to 'z'. This avoids redundant substring checks.
*   **Count Unique Substrings:** Finally, we sum up the values in the `max_len` structure to get the total number of unique substrings.

*   **Time Complexity:** O(n), where n is the length of the string `s`.
*   **Space Complexity:** O(1). We only need space for 26 characters.

	
	# Code
	```python
	def find_substrings_in_wraparound_string(s: str) -> int:
    """
    Calculates the number of unique non-empty substrings of s that are present in the infinite wraparound string.

    Args:
        s: The input string consisting of lowercase English letters.

    Returns:
        The number of unique non-empty substrings of s that are present in the base.
    """

    max_len = {}  # Dictionary to store the max length of substring ending with each character
    current_len = 0

    for i in range(len(s)):
        if i > 0 and (ord(s[i]) - ord(s[i - 1]) == 1 or (s[i - 1] == 'z' and s[i] == 'a')):
            current_len += 1
        else:
            current_len = 1

        char = s[i]
        max_len[char] = max(max_len.get(char, 0), current_len)

    return sum(max_len.values())
	```