3557. Find Maximum Number of Non Intersecting Substrings
Description
You are given a string word.
Return the maximum number of non-intersecting substrings of word that are at least four characters long and start and end with the same letter.
Example 1:
Input: word = "abcdeafdef"
Output: 2
Explanation:
The two substrings are "abcdea" and "fdef".
Example 2:
Input: word = "bcdaaaab"
Output: 1
Explanation:
The only substring is "aaaa". Note that we cannot also choose "bcdaaaab" since it intersects with the other substring.
Constraints:
1 <= word.length <= 2 * 105wordconsists only of lowercase English letters.
Solutions
Solution 1
Thinking
A substring must start and end with the same letter and have length at least \(4\); selected ones must be disjoint. \(n \le 2 \cdot 10^5\) forbids enumerating intervals.
Scan left to right. Remember the last unused start of each letter; when the current index is at least \(3\) past that start, take the piece and clear the start. Finishing a short piece early never blocks a later choice, so the count is maximal.
1 | |
1 | |
1 | |
1 | |