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.

#467

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

环绕字符串中唯一的子字符串

定义字符串 base 为一个 "abcdefghijklmnopqrstuvwxyz" 无限环绕的字符串，所以 base 看起来是这样的： "...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd...." . 给你一个字符串 s ，…

字符串动态规划

题目描述

定义字符串 base 为一个 "abcdefghijklmnopqrstuvwxyz" 无限环绕的字符串，所以 base 看起来是这样的：

"...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd....".

给你一个字符串 s ，请你统计并返回 s 中有多少不同非空子串 也在 base 中出现。

示例 1：

输入：s = "a"
输出：1
解释：字符串 s 的子字符串 "a" 在 base 中出现。

示例 2：

输入：s = "cac"
输出：2
解释：字符串 s 有两个子字符串 ("a", "c") 在 base 中出现。

示例 3：

输入：s = "zab"
输出：6
解释：字符串 s 有六个子字符串 ("z", "a", "b", "za", "ab", and "zab") 在 base 中出现。

提示：

1 <= s.length <= 10⁵
s 由小写英文字母组成

lightbulb

解题思路

方法一：动态规划

我们不妨定义一个长度为 $26$ 的数组 $f$ ，其中 $f[i]$ 表示以第 $i$ 个字符结尾的最长连续子串的长度。那么答案就是 $f$ 中所有元素的和。

我们定义一个变量 $k$ ，表示以当前字符结尾的最长连续子串的长度。遍历字符串 $s$ ，对于每个字符 $c$ ，如果 $c$ 和前一个字符 $s[i - 1]$ 之间的差值为 $1$ ，那么 $k$ 就加 $1$ ，否则 $k$ 重置为 $1$ 。然后更新 $f[c]$ 为 $f[c]$ 和 $k$ 的较大值。

最后返回 $f$ 中所有元素的和即可。

时间复杂度 $O(n)$ ，其中 $n$ 是字符串 $s$ 的长度。空间复杂度 $O(|\Sigma|)$ ，其中 $\Sigma$ 是字符集，这里是小写字母集合。

1

2

3

4

5

6

7

8

9

10

11

12

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())

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

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

warning

常见陷阱

外企场景

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

swap_horiz

进阶变体

外企场景

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

help

常见问题

外企场景

继续练习

#466 统计重复个数 #472 连接词 #474 一和零