What is the primary pattern in the 'Maximum Number of Non-Overlapping Substrings' problem?

The problem follows a greedy approach where you select substrings based on non-overlap, ensuring the total length is minimized.

How do I know if two substrings overlap in the 'Maximum Number of Non-Overlapping Substrings' problem?

You can check if two substrings overlap by comparing their start and end indices. If one substring’s range intersects the other’s, they overlap.

What is the significance of selecting the minimum total length in the problem?

Selecting the minimum total length ensures that you return the optimal solution when multiple valid combinations of substrings are possible.

How does the greedy algorithm apply to 'Maximum Number of Non-Overlapping Substrings'?

The greedy algorithm helps prioritize selecting non-overlapping substrings that are the smallest possible, minimizing the total length while maximizing the count.

What happens if substrings are allowed to overlap in this problem?

Allowing substrings to overlap would change the problem's constraints, potentially leading to multiple valid solutions, but it would complicate substring selection.

#1520

Hard

auto_awesome贪心·invariant

LeetCode 题解工作台

最多的不重叠子字符串

给你一个只包含小写字母的字符串 s ，你需要找到 s 中最多数目的非空子字符串，满足如下条件：这些字符串之间互不重叠，也就是说对于任意两个子字符串 s[i..j] 和 s[x..y] ，要么 j 要么 i > y 。如果一个子字符串包含字符 char ，那么 s 中所有 char 字符都应该在这…

字符串贪心

题目描述

给你一个只包含小写字母的字符串 s ，你需要找到 s 中最多数目的非空子字符串，满足如下条件：

这些字符串之间互不重叠，也就是说对于任意两个子字符串 s[i..j] 和 s[x..y] ，要么 j < x 要么 i > y 。
如果一个子字符串包含字符 char ，那么 s 中所有 char 字符都应该在这个子字符串中。

请你找到满足上述条件的最多子字符串数目。如果有多个解法有相同的子字符串数目，请返回这些子字符串总长度最小的一个解。可以证明最小总长度解是唯一的。

请注意，你可以以任意顺序返回最优解的子字符串。

示例 1：

输入：s = "adefaddaccc"
输出：["e","f","ccc"]
解释：下面为所有满足第二个条件的子字符串：
[
  "adefaddaccc"
  "adefadda",
  "ef",
  "e",
  "f",
  "ccc",
]
如果我们选择第一个字符串，那么我们无法再选择其他任何字符串，所以答案为 1 。如果我们选择 "adefadda" ，剩下子字符串中我们只可以选择 "ccc" ，它是唯一不重叠的子字符串，所以答案为 2 。同时我们可以发现，选择 "ef" 不是最优的，因为它可以被拆分成 2 个子字符串。所以最优解是选择 ["e","f","ccc"] ，答案为 3 。不存在别的相同数目子字符串解。

示例 2：

输入：s = "abbaccd"
输出：["d","bb","cc"]
解释：注意到解 ["d","abba","cc"] 答案也为 3 ，但它不是最优解，因为它的总长度更长。

提示：

1 <= s.length <= 10^5
s 只包含小写英文字母。

lightbulb

解题思路

方法一

1

2

speed

复杂度分析

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

psychology

面试官常问的追问

外企场景

question_mark
Evaluates understanding of greedy algorithms and invariant validation.
question_mark
Tests ability to optimize substring selection for minimum length.
question_mark
Checks for efficiency in handling large strings with non-overlapping substring constraints.

warning

常见陷阱

外企场景

error
Choosing substrings that overlap, which violates the problem’s constraints.
error
Failing to track the starting and ending indices of chosen substrings.
error
Not considering all valid substring combinations with the same number of substrings.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Modify the problem to allow overlapping substrings and ask how the approach changes.
arrow_right_alt
Increase the size of the string and test how efficiently the algorithm handles larger inputs.
arrow_right_alt
Change the string to include repeating characters and check how that affects substring selection.

help

常见问题

外企场景

继续练习

#1529 最少的后缀翻转次数 #1505 最多 K 次交换相邻数位后得到的最小整数 #1541 平衡括号字符串的最少插入次数