# Find Maximum Number of Non Intersecting Substrings
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-maximum-number-of-non-intersecting-substrings)
Canonical: https://scaleengineer.com/dsa/problems/find-maximum-number-of-non-intersecting-substrings
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** Hash Table, String
---
## Problem
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 * 105`
* `word` consists only of lowercase English letters.

# Approaches
## Brute-Force Recursive Approach
This approach uses recursion to explore all possible combinations of valid non-intersecting substrings. It tries every possibility at each character: either skip it or form a valid substring starting with it. This exhaustive search ensures correctness but at a very high computational cost.
**Time:** O(2^n), where n is the length of the string. In the worst case, the recursive calls branch out, leading to an exponential number of states to explore. · **Space:** O(n), where n is the length of the string. This is for the recursion stack depth in the worst case.
**Pros:** Conceptually simple and directly follows the problem definition.
**Cons:** Extremely inefficient due to a large number of redundant computations.; Will result in a 'Time Limit Exceeded' error for the given constraints.
### Explanation
A recursive function `solve(startIndex)` is designed to calculate the maximum number of valid substrings from the suffix `word[startIndex...]`. The function considers two main choices:

1.  **Skip:** We don't start a substring at `startIndex`. The problem reduces to finding the maximum substrings in the rest of the string, which is given by a recursive call `solve(startIndex + 1)`.
2.  **Include:** We try to form a valid substring starting at `startIndex`. A substring is valid if it's at least 4 characters long and starts and ends with the same letter. We iterate through all possible end indices `j` from `startIndex + 3` onwards. If `word.charAt(startIndex) == word.charAt(j)`, we have a valid substring `[startIndex, j]`. We can take this substring and then recursively find the maximum number of substrings in the remaining part of the string, which starts from `j + 1`. This choice gives a total of `1 + solve(j + 1)` substrings.

The function takes the maximum over all these possibilities. Since the same subproblems (e.g., `solve(k)` for some `k`) are solved multiple times, the algorithm has an exponential time complexity.

```java
public int solve(String word, int startIndex) {
    if (startIndex >= word.length()) {
        return 0;
    }

    // Option 1: Don't start a substring at startIndex
    int maxCount = solve(word, startIndex + 1);

    // Option 2: Try to form a valid substring starting at startIndex
    for (int j = startIndex + 3; j < word.length(); j++) {
        if (word.charAt(startIndex) == word.charAt(j)) {
            maxCount = Math.max(maxCount, 1 + solve(word, j + 1));
        }
    }

    return maxCount;
}
```
### Algorithm
*   Define a recursive function, say `solve(startIndex)`, that computes the maximum number of valid non-intersecting substrings in the suffix of the string starting from `startIndex`.
*   The base case for the recursion is when `startIndex` is greater than or equal to the string length, in which case we return 0 as no more substrings can be formed.
*   For a given `startIndex`, there are two possibilities:
    1.  We do not start a substring at `startIndex`. In this case, the result is `solve(startIndex + 1)`.
    2.  We try to form a valid substring starting at `startIndex`. We iterate through all possible end indices `j` from `startIndex + 3` to `n-1`. If `word[startIndex] == word[j]`, we have found a valid substring. The number of substrings for this choice is `1 + solve(j + 1)`.
*   The function `solve(startIndex)` returns the maximum value among all these possibilities.
*   The initial call to start the process is `solve(0)`.

## Generate All Intervals and Apply Greedy Selection
This approach models the problem as a classic interval scheduling problem. First, we generate all possible valid substrings and represent each as an interval `[start, end]`. Then, we apply a standard greedy algorithm to find the maximum number of non-overlapping intervals from this set.
**Time:** O(n^2 log n). Generating all intervals takes O(n^2). Sorting O(n^2) intervals takes O(n^2 log(n^2)) which simplifies to O(n^2 log n). · **Space:** O(n^2), to store the list of all possible valid intervals.
**Pros:** Reduces the problem to a standard, well-understood algorithm (Interval Scheduling).; More structured and efficient than pure brute-force recursion.
**Cons:** The number of valid substrings can be up to O(n^2), leading to high time and space complexity.; Inefficient for the given constraints due to the O(n^2) factor.
### Explanation
The core of this method is to transform the problem into a well-known one: finding the maximum number of non-overlapping intervals.

1.  **Interval Generation:** We exhaustively search for all valid substrings. A substring from index `i` to `j` is valid if it starts and ends with the same character (`word[i] == word[j]`) and has a length of at least 4 (`j - i + 1 >= 4`). Each such valid substring is stored as an interval `[i, j]`. This can result in up to O(n^2) intervals.

2.  **Greedy Algorithm (Activity Selection):** To find the maximum number of non-overlapping intervals, a greedy strategy is optimal. The strategy is to always pick the interval that finishes first. By sorting all intervals by their end points, we can iterate through them and pick an interval if it doesn't overlap with the last one we picked. An interval `[start, end]` doesn't overlap with the last picked interval (which ended at `lastEnd`) if `start > lastEnd`.

```java
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

class Solution {
    public int maxNumOfSubstrings(String word) {
        int n = word.length();
        List<int[]> intervals = new ArrayList<>();

        // 1. Generate all valid intervals
        for (int i = 0; i < n; i++) {
            for (int j = i + 3; j < n; j++) {
                if (word.charAt(i) == word.charAt(j)) {
                    intervals.add(new int[]{i, j});
                }
            }
        }

        if (intervals.isEmpty()) {
            return 0;
        }

        // 2. Sort intervals by end point
        intervals.sort(Comparator.comparingInt(a -> a[1]));

        // 3. Greedy selection
        int count = 1;
        int lastEnd = intervals.get(0)[1];

        for (int i = 1; i < intervals.size(); i++) {
            int[] currentInterval = intervals.get(i);
            if (currentInterval[0] > lastEnd) {
                count++;
                lastEnd = currentInterval[1];
            }
        }

        return count;
    }
}
```
### Algorithm
*   **Step 1: Generate All Valid Intervals**
    *   Create an empty list to store intervals.
    *   Use nested loops to iterate through all possible pairs of indices `(i, j)` with `0 <= i < n` and `i + 3 <= j < n`.
    *   If `word.charAt(i) == word.charAt(j)`, a valid substring `word[i...j]` is found. Add the interval `[i, j]` to the list.
*   **Step 2: Sort Intervals**
    *   Sort the list of generated intervals based on their end points in ascending order.
*   **Step 3: Greedy Selection**
    *   Initialize `count = 0` and `lastEnd = -1`.
    *   Iterate through the sorted intervals `[start, end]`.
    *   If `start > lastEnd`, the current interval does not overlap with the previously selected one. Select it by incrementing `count` and updating `lastEnd = end`.
*   **Step 4: Return Result**
    *   Return `count`.

## Optimized Interval Generation with Greedy Selection
This approach significantly optimizes the interval generation step of the previous method. Instead of generating all O(n^2) possible valid substrings, we observe that for any given starting point, it's always optimal to choose the shortest possible valid substring. This reduces the number of intervals to consider to at most `n`, making the subsequent sorting and selection steps much faster.
**Time:** O(n log n). O(n) to build the position map. O(n log k) to generate intervals, where k is the max frequency of a character (k<=n), so O(n log n). O(n log n) to sort the intervals. The greedy pass is O(n). · **Space:** O(n), to store the character positions and the O(n) generated intervals.
**Pros:** Drastically reduces the number of intervals from O(n^2) to O(n).; Achieves a much better time complexity of O(n log n), which is efficient enough for the given constraints.
**Cons:** The implementation is more complex than the previous approach, involving data structures and binary search.; The O(n log n) complexity might still be too slow for extremely large N, though it passes the given constraints.
### Explanation
The key insight here is that we don't need to consider all valid substrings. For a fixed start `i`, consider two valid substrings `S1 = word[i...j1]` and `S2 = word[i...j2]` with `j1 < j2`. If we choose `S1`, the next non-overlapping substring can start from `j1 + 1`. If we choose `S2`, it can only start from `j2 + 1`. Since `j1 + 1 < j2 + 1`, choosing `S1` (the shorter substring) provides more opportunities for subsequent substrings. Thus, we only need to generate one interval per starting position: `[i, j_min]`, where `j_min` is the smallest valid end index.

To implement this, we can precompute the indices of all characters. A `HashMap` mapping each character to a sorted list of its indices works well. For each starting index `i`, we look up the list for `word.charAt(i)` and use binary search to find the first index `j` in that list that is greater than or equal to `i + 3`. This process gives us a list of at most `n` 'optimal' intervals, which we can then solve using the standard greedy interval scheduling algorithm.

```java
// This is a conceptual snippet. A full implementation would require
// a binary search helper function.
List<int[]> intervals = new ArrayList<>();
Map<Character, List<Integer>> positions = new HashMap<>();
for (int i = 0; i < n; i++) {
    positions.computeIfAbsent(word.charAt(i), k -> new ArrayList<>()).add(i);
}

for (int i = 0; i < n; i++) {
    char c = word.charAt(i);
    List<Integer> posList = positions.get(c);
    // Perform binary search on posList to find the smallest index j >= i + 3
    int j_min = findFirstIndexGreaterThanOrEqualTo(posList, i + 3);
    if (j_min != -1) {
        intervals.add(new int[]{i, j_min});
    }
}

// Sort and apply greedy selection on the 'intervals' list as before.
// ...
```
### Algorithm
*   **Step 1: Prune the intervals.** For any starting index `i`, if there are multiple valid substrings `[i, j1], [i, j2], ...`, the one with the smallest end point is always the best choice because it leaves the most room for subsequent substrings. So, for each `i`, we only need to find the smallest `j >= i + 3` such that `word[i] == word[j]`.
*   **Step 2: Efficiently find minimal end points.** To find these minimal `j`'s efficiently, we can pre-process the string. One way is to store the indices of each character in a hash map (`Map<Character, List<Integer>>`). Then for each `i`, we can perform a binary search on the list of indices for `word[i]` to find the smallest index `j >= i + 3`.
*   **Step 3: Generate O(n) intervals.** Iterate from `i = 0` to `n-1`, find the minimal `j` for each `i` as described above, and add the interval `[i, j]` to a list. This creates at most `n` intervals.
*   **Step 4: Apply greedy selection.** Sort these `O(n)` intervals by their end points and apply the same greedy selection algorithm as in the previous approach.

## Dynamic Programming
The most efficient solution uses dynamic programming. We build the solution from right to left. We define `dp[i]` as the maximum number of valid non-intersecting substrings that can be found in the suffix of the string starting at index `i`. By considering whether to start a new substring at each index `i` or not, we can build up the solution in linear time.
**Time:** O(n * k), where k is the alphabet size. Precomputation takes O(n*k) and the DP loop takes O(n). Since k is a constant (26), the total time complexity is O(n). · **Space:** O(n * k), where n is the string length and k is the alphabet size (26). This is for the `next` table and the `dp` array. Since k is constant, this is O(n).
**Pros:** Optimal time complexity of O(n).; Directly solves the problem without transforming it to another problem like interval scheduling.
**Cons:** Requires more space for the precomputation table compared to an O(n log n) approach that doesn't use one.; The logic can be slightly less intuitive than the interval-based approaches.
### Explanation
This approach avoids generating and sorting intervals altogether. We iterate from the end of the string to the beginning, making a decision at each character.

Let `dp[i]` be the maximum number of valid substrings in `word[i...n-1]`. Our goal is to find `dp[0]`. The base cases are `dp[n] = 0` and `dp[n+1] = 0`.

For each index `i` from `n-1` down to `0`, we have two choices:
1.  We don't start a substring at `i`. The maximum number of substrings is then the same as the solution for the suffix `word[i+1...n-1]`, which is `dp[i+1]`.
2.  We start a substring at `i`. To maximize the total count, we should choose the shortest possible valid substring starting at `i`, as this leaves the most room for subsequent substrings. We need to find the smallest index `j >= i + 3` such that `word[i] == word[j]`. If we find such a `j`, we take this substring, and the total count becomes `1 + dp[j+1]`.

To find this `j` efficiently, we precompute a `next[k][c]` table, which gives the index of the first occurrence of character `c` at or after index `k`. This allows finding `j` in O(1) time. The overall DP calculation then takes O(n) time.

```java
class Solution {
    public int maxNumOfSubstrings(String word) {
        int n = word.length();
        if (n < 4) {
            return 0;
        }

        // next[i][char_code] = index of first occurrence of char at or after index i
        int[][] next = new int[n + 1][26];
        for (int j = 0; j < 26; j++) {
            next[n][j] = n; // Sentinel for not found
        }

        for (int i = n - 1; i >= 0; i--) {
            for (int j = 0; j < 26; j++) {
                next[i][j] = next[i + 1][j];
            }
            next[i][word.charAt(i) - 'a'] = i;
        }

        int[] dp = new int[n + 2]; // dp[n] and dp[n+1] are implicitly 0

        for (int i = n - 1; i >= 0; i--) {
            // Option 1: Don't start a substring at i
            dp[i] = dp[i + 1];

            // Option 2: Start a substring at i
            int charCode = word.charAt(i) - 'a';
            int requiredStartIndexForJ = i + 3;

            if (requiredStartIndexForJ < n) {
                int j = next[requiredStartIndexForJ][charCode];
                if (j < n) {
                    // Found a valid substring [i, j]
                    dp[i] = Math.max(dp[i], 1 + dp[j + 1]);
                }
            }
        }

        return dp[0];
    }
}
```
### Algorithm
*   **Step 1: Precomputation.** Create a 2D array `next[i][char]` that stores the index of the first occurrence of `char` at or after index `i`. This can be computed in O(n * alphabet_size) by iterating backwards from the end of the string.
*   **Step 2: Define DP State.** Let `dp[i]` be the maximum number of non-intersecting valid substrings in the suffix `word[i...n-1]`.
*   **Step 3: DP Recurrence.** We compute `dp` values from `i = n-1` down to `0`. For each `i`, `dp[i]` is the maximum of two choices:
    1.  **Skip `i`**: Don't start a substring at `i`. The result is `dp[i+1]`.
    2.  **Start at `i`**: Find the smallest index `j >= i + 3` where `word[j] == word[i]`. This `j` can be found in O(1) using our precomputed `next` table: `j = next[i+3][word[i]]`. If such a `j` exists, this choice yields `1 + dp[j+1]` substrings.
    *   The recurrence is `dp[i] = max(dp[i+1], 1 + dp[j+1])`.
*   **Step 4: Final Answer.** The result for the whole string is `dp[0]`.