3557. Find Maximum Number of Non Intersecting Substrings

Problem Link

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.

A substring is a contiguous non-empty sequence of characters within a string.

 

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 * 105
• word consists only of lowercase English letters.

Solution

---

Python3

class Solution:
    def maxSubstrings(self, word: str) -> int:
        N = len(word)
        A = defaultdict(list)
 
        for i, x in enumerate(word):
            A[x].append(i)
 
        @cache
        def go(index):
            if index >= N:
                return 0
 
            # skip
            res = go(index + 1)
            
            idx = bisect_right(A[word[index]], index + 2)
            if idx < len(A[word[index]]):
                res = max(res, 1 + go(A[word[index]][idx] + 1))
 
            return res
 
        return go(0)