How do I apply state transition dynamic programming to solve this problem?

State transition dynamic programming involves storing the results of previously computed states and using them to transition to the next state. In this problem, the states represent the sum of unique characters in substrings, and the transition is managed by tracking character occurrences.

What is the most efficient way to handle repeated substrings?

The most efficient approach is to use a hash map to track the last occurrence of each character and adjust the starting index of the substring accordingly to ensure only unique characters are counted.

How can I optimize my solution for larger input sizes?

To optimize the solution, use dynamic programming to avoid redundant calculations and a sliding window to efficiently track the valid substrings. These techniques help reduce both time and space complexity.

What is the time complexity of this solution?

The time complexity is O(n), where n is the length of the string. This is because each character is processed once with efficient state transitions using dynamic programming and a hash map.

What if the string contains repeated characters or is large?

For strings with repeated characters or large input sizes, it's essential to optimize using dynamic programming and sliding windows. This ensures that we only compute the unique characters once for each substring.

#828

Hard

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

统计子串中的唯一字符

我们定义了一个函数 countUniqueChars(s) 来统计字符串 s 中的唯一字符，并返回唯一字符的个数。例如： s = "LEETCODE" ，则其中 "L" , "T" , "C" , "O" , "D" 都是唯一字符，因为它们只出现一次，所以 countUniqueChars(s) …

哈希表字符串动态规划

题目描述

我们定义了一个函数 countUniqueChars(s) 来统计字符串 s 中的唯一字符，并返回唯一字符的个数。

例如：s = "LEETCODE" ，则其中 "L", "T","C","O","D" 都是唯一字符，因为它们只出现一次，所以 countUniqueChars(s) = 5 。

本题将会给你一个字符串 s ，我们需要返回 countUniqueChars(t) 的总和，其中 t 是 s 的子字符串。输入用例保证返回值为 32 位整数。

注意，某些子字符串可能是重复的，但你统计时也必须算上这些重复的子字符串（也就是说，你必须统计 s 的所有子字符串中的唯一字符）。

示例 1：

输入: s = "ABC"
输出: 10
解释: 所有可能的子串为："A","B","C","AB","BC" 和 "ABC"。
     其中，每一个子串都由独特字符构成。
     所以其长度总和为：1 + 1 + 1 + 2 + 2 + 3 = 10

示例 2：

输入: s = "ABA"
输出: 8
解释: 除了 countUniqueChars("ABA") = 1 之外，其余与示例 1 相同。

示例 3：

输入：s = "LEETCODE"
输出：92

提示：

1 <= s.length <= 10⁵
s 只包含大写英文字符

lightbulb

解题思路

方法一：计算每个字符的贡献

对于字符串 $s$ 的每个字符 $c_i$ ，当它在某个子字符串中仅出现一次时，它会对这个子字符串统计唯一字符时有贡献。

因此，我们只需要对每个字符 $c_i$ ，计算有多少子字符串仅包含该字符一次即可。

我们用一个哈希表或者长度为 $26$ 的数组 $d$ ，按照下标顺序存储每个字符在 $s$ 中所有出现的位置。

对于每个字符 $c_i$ ，我们遍历 $d[c_i]$ 中的每个位置 $p$ ，找出左侧相邻的位置 $l$ 和右侧相邻的位置 $r$ ，那么从位置 $p$ 向左右两边扩散，满足要求的子字符串的数量就是 $(p - l) \times (r - p)$ 。我们对每个字符都进行这样的操作，累加所有字符的贡献，即可得到答案。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为字符串 $s$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def uniqueLetterString(self, s: str) -> int:
        d = defaultdict(list)
        for i, c in enumerate(s):
            d[c].append(i)
        ans = 0
        for v in d.values():
            v = [-1] + v + [len(s)]
            for i in range(1, len(v) - 1):
                ans += (v[i] - v[i - 1]) * (v[i + 1] - v[i])
        return ans

speed

复杂度分析

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

psychology

面试官常问的追问

外企场景

question_mark
Look for understanding of dynamic programming and state transitions in string problems.
question_mark
Assess how the candidate uses hash maps or sliding windows to manage repeated characters.
question_mark
Check if the candidate can optimize the solution to avoid recalculating substrings unnecessarily.

warning

常见陷阱

外企场景

error
Not accounting for repeated substrings and recalculating unique characters multiple times.
error
Failing to efficiently track character occurrences with a hash map, leading to higher time complexity.
error
Overcomplicating the solution by neglecting the sliding window or dynamic programming optimization.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Consider extending the problem to handle strings with lowercase letters or special characters.
arrow_right_alt
Modify the problem to count the total number of unique characters across substrings that have specific lengths.
arrow_right_alt
Explore how the solution can be adapted to substrings that need to be palindromes or contain a specific number of characters.

help

常见问题

外企场景

继续练习

#792 匹配子序列的单词数 #691 贴纸拼词 #1048 最长字符串链