HardNo. 1520
Maximum Number of Non-Overlapping Substrings — LeetCode 1520 Python Solution
- Pattern
- Greedy
- Topics
- Greedy, String
- Reading time
- 2 min
- Source
- leetcode.com
The problem
Given a string s of lowercase letters, you need to find the maximum number of non-empty substrings of s that meet the following conditions: The substrings do not overlap, that is for any two substrings s[i..j] and s[x..y], either j < x or i > y is true. A substring that contains a certain character c must also contain all occurrences of c.
Example
- Input
- s = "adefaddaccc"
- Output
- ["e","f","ccc"]
- Explanation
- The following are all the possible substrings that meet the conditions:
Complexity
- Time
- O(n log n)
- Space · auxiliary
- O(1) to O(n)
Pattern: Greedy
Take the locally best option every time — when you can prove that never costs you later. LeetCode 1520. Maximum Number of Non-Overlapping Substrings is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Greedy.
The greedy guide has the Python template for the pattern and the 346 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 1529 | Minimum Suffix Flips | Medium |
| 0179 | Largest Number | Medium |
| 0316 | Remove Duplicate Letters | Medium |
| 0402 | Remove K Digits | Medium |
| 0420 | Strong Password Checker | Hard |
| 0649 | Dota2 Senate | Medium |
Frequently asked questions
- How hard is LeetCode 1520. Maximum Number of Non-Overlapping Substrings?
LeetCode 1520. Maximum Number of Non-Overlapping Substrings is rated Hard on LeetCode.
- What topics does LeetCode 1520. Maximum Number of Non-Overlapping Substrings cover?
LeetCode 1520. Maximum Number of Non-Overlapping Substrings is tagged Greedy and String on LeetCode.