#467

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Unique Substrings in Wraparound String

Solve the 'Unique Substrings in Wraparound String' problem using dynamic programming with a state transition approach.

Problem Statement

You are given a string s and a base string defined as an infinite wraparound string of lowercase English letters 'abcdefghijklmnopqrstuvwxyz'. You need to return the number of unique non-empty substrings of s that are present in the base string. For example, if s is 'zab', the answer would be 6 because the substrings 'z', 'a', 'b', 'za', 'ab', and 'zab' all appear in the wraparound string.

The challenge is to efficiently compute the result given the constraint that s can be up to 10^5 characters long. A brute-force approach would not work within the time limits, and thus, dynamic programming becomes essential. One of the most efficient methods to solve this problem is through a state transition dynamic programming approach, which maintains an array of length 26 (for each character in the alphabet) to keep track of the lengths of longest substrings that end with each letter.

Examples

Example 1

Input: s = "a"

Output: 1

Only the substring "a" of s is in base.

Example 2

Input: s = "cac"

Output: 2

There are two substrings ("a", "c") of s in base.

Example 3

Input: s = "zab"

Output: 6

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.

Solution Approach

Dynamic Programming Array

Create an array dp of size 26, where each element corresponds to the longest valid substring that ends with a specific character. Iterate through the string s, and for each character, calculate the maximum number of substrings that can be formed by extending the existing valid substrings or starting a new one.

State Transition Update

As you process each character, update the dp array using the previous character in the base string. For each character, if it continues from the previous character in the wraparound string (i.e., the previous character is alphabetically adjacent), increase the count. Otherwise, start a new count of substrings for that character.

Sum Up the Results

After processing the string, sum all values in the dp array to get the total count of unique substrings that appear in the infinite wraparound string.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of the solution is O(n), where n is the length of the string s, because each character is processed once and the updates to the dp array take constant time. The space complexity is O(1), as the array dp has a fixed size of 26, regardless of the input size.

What Interviewers Usually Probe

Candidate demonstrates understanding of dynamic programming and efficient state transitions.
Candidate suggests using a fixed-size array for the 26 alphabet characters, optimizing space complexity.
Candidate avoids brute-force solutions and is aware of the time constraints, emphasizing efficiency.

Common Pitfalls or Variants

Common pitfalls

Not utilizing dynamic programming to track longest substrings, leading to inefficient solutions.
Mismanaging the dp array, causing incorrect substring length updates.
Failing to consider the circular nature of the wraparound string, which may lead to overlooked substring connections.

Follow-up variants

Modifying the base string to be a different cyclic sequence, such as '0123456789'.
Considering uppercase English letters in the string s.
Allowing for multiple string queries, where each query involves calculating the unique substrings for a different string s.

FAQ

How does dynamic programming solve the 'Unique Substrings in Wraparound String' problem?

Dynamic programming optimizes the solution by tracking the longest substrings ending at each letter in the alphabet and avoiding redundant recalculations.

What is the space complexity of the 'Unique Substrings in Wraparound String' problem?

The space complexity is O(1) because the solution uses a fixed-size array of 26 elements to store the counts of substrings for each character.

Why is a brute-force solution not feasible for the 'Unique Substrings in Wraparound String' problem?

A brute-force approach would involve checking every possible substring of the input string, which would be inefficient given the constraint of up to 10^5 characters in the string.

What is the optimal data structure for solving the 'Unique Substrings in Wraparound String' problem?

The optimal data structure is a fixed-size array of 26 elements to track the longest substrings for each letter in the alphabet.

What does 'wraparound string' mean in the context of this problem?

A wraparound string refers to an infinite sequence of characters formed by repeating the string 'abcdefghijklmnopqrstuvwxyz' in a circular manner.

terminal

Solution

Solution 1: Dynamic Programming

We can define an array $f$ of length $26$, where $f[i]$ represents the length of the longest consecutive substring ending with the $i$th character. The answer is the sum of all elements in $f$.

class Solution:
    def findSubstringInWraproundString(self, s: str) -> int:
        f = defaultdict(int)
        k = 0
        for i, c in enumerate(s):
            if i and (ord(c) - ord(s[i - 1])) % 26 == 1:
                k += 1
            else:
                k = 1
            f[c] = max(f[c], k)
        return sum(f.values())

Continue Practicing

#466 count the repetitions #472 concatenated words #474 ones and zeroes