Find Maximum Number of Non Intersecting Substrings - Solution & Explanation

Problem Overview: Given a string s, return the maximum number of substrings that do not overlap such that every character inside a chosen substring appears only within that substring in the entire string. Among all valid sets, the solution prefers the set with the maximum count of substrings.

Approach 1: Brute Force Substring Validation (O(n^3) time, O(1) space)

Enumerate every possible substring using two nested loops. For each candidate substring s[i..j], scan the whole string to verify that every character inside the substring does not appear outside the interval. After collecting all valid substrings, sort them by ending index and greedily pick non‑overlapping ones. This approach performs repeated scans of the string, leading to cubic complexity. Useful only for understanding the constraint that every character's global occurrences must lie inside the chosen interval.

Approach 2: Character Range Expansion (Greedy + Hash Table) (O(26 * n) ≈ O(n) time, O(1) space)

Precompute the first and last occurrence of each character using a hash table or fixed array of size 26. For every character's first occurrence, treat its interval [start, end] as a candidate substring. Expand the interval by iterating from start to end; if a character inside has a last occurrence beyond end, extend the boundary. If any character inside appears before start, the interval is invalid and must be discarded. Valid intervals represent minimal substrings that contain all occurrences of their characters. Collect these intervals and select the maximum number of non-overlapping ones by sorting by end index and greedily choosing the earliest finishing interval. This leverages ideas from greedy interval scheduling combined with string preprocessing.

Approach 3: Dynamic Programming with Interval Candidates (O(n + k log k) time, O(k) space)

After generating all valid minimal intervals using the expansion method, treat them as interval scheduling candidates. Use dynamic programming or greedy selection based on sorted end indices. DP can track the maximum number of substrings achievable up to each interval while ensuring non-overlap. In practice, the greedy strategy (pick the earliest ending valid substring) already yields the optimal result because minimal intervals never partially overlap in a way that benefits delaying the choice.

Recommended for interviews: The interval expansion + greedy selection approach is what interviewers expect. It demonstrates understanding of character frequency boundaries, interval construction, and classic greedy scheduling. Starting with brute force shows the constraint clearly, but the optimized O(n) solution proves you can combine preprocessing with greedy reasoning efficiently.