Find Maximum Number of Non Intersecting Substrings

• 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).

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.

1public int solve(String word, int startIndex) {2    if (startIndex >= word.length()) {3        return 0;4    }5 6    // Option 1: Don't start a substring at startIndex7    int maxCount = solve(word, startIndex + 1);8 9    // Option 2: Try to form a valid substring starting at startIndex10    for (int j = startIndex + 3; j < word.length(); j++) {11        if (word.charAt(startIndex) == word.charAt(j)) {12            maxCount = Math.max(maxCount, 1 + solve(word, j + 1));13        }14    }15 16    return maxCount;17}

• 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.

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.

1import java.util.ArrayList;2import java.util.Collections;3import java.util.Comparator;4import java.util.List;5 6class Solution {7    public int maxNumOfSubstrings(String word) {8        int n = word.length();9        List<int[]> intervals = new ArrayList<>();10 11        // 1. Generate all valid intervals12        for (int i = 0; i < n; i++) {13            for (int j = i + 3; j < n; j++) {14                if (word.charAt(i) == word.charAt(j)) {15                    intervals.add(new int[]{i, j});16                }17            }18        }19 20        if (intervals.isEmpty()) {21            return 0;22        }23 24        // 2. Sort intervals by end point25        intervals.sort(Comparator.comparingInt(a -> a[1]));26 27        // 3. Greedy selection28        int count = 1;29        int lastEnd = intervals.get(0)[1];30 31        for (int i = 1; i < intervals.size(); i++) {32            int[] currentInterval = intervals.get(i);33            if (currentInterval[0] > lastEnd) {34                count++;35                lastEnd = currentInterval[1];36            }37        }38 39        return count;40    }41}

• 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.

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.

1// This is a conceptual snippet. A full implementation would require2// a binary search helper function.3List<int[]> intervals = new ArrayList<>();4Map<Character, List<Integer>> positions = new HashMap<>();5for (int i = 0; i < n; i++) {6    positions.computeIfAbsent(word.charAt(i), k -> new ArrayList<>()).add(i);7}8 9for (int i = 0; i < n; i++) {10    char c = word.charAt(i);11    List<Integer> posList = positions.get(c);12    // Perform binary search on posList to find the smallest index j >= i + 313    int j_min = findFirstIndexGreaterThanOrEqualTo(posList, i + 3);14    if (j_min != -1) {15        intervals.add(new int[]{i, j_min});16    }17}18 19// Sort and apply greedy selection on the 'intervals' list as before.20// ...

• 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].

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.

1class Solution {2    public int maxNumOfSubstrings(String word) {3        int n = word.length();4        if (n < 4) {5            return 0;6        }7 8        // next[i][char_code] = index of first occurrence of char at or after index i9        int[][] next = new int[n + 1][26];10        for (int j = 0; j < 26; j++) {11            next[n][j] = n; // Sentinel for not found12        }13 14        for (int i = n - 1; i >= 0; i--) {15            for (int j = 0; j < 26; j++) {16                next[i][j] = next[i + 1][j];17            }18            next[i][word.charAt(i) - 'a'] = i;19        }20 21        int[] dp = new int[n + 2]; // dp[n] and dp[n+1] are implicitly 022 23        for (int i = n - 1; i >= 0; i--) {24            // Option 1: Don't start a substring at i25            dp[i] = dp[i + 1];26 27            // Option 2: Start a substring at i28            int charCode = word.charAt(i) - 'a';29            int requiredStartIndexForJ = i + 3;30 31            if (requiredStartIndexForJ < n) {32                int j = next[requiredStartIndexForJ][charCode];33                if (j < n) {34                    // Found a valid substring [i, j]35                    dp[i] = Math.max(dp[i], 1 + dp[j + 1]);36                }37            }38        }39 40        return dp[0];41    }42}