Select K Disjoint Special Substrings - Solution & Explanation

Problem Overview: Given a string s and an integer k, select k disjoint substrings such that each substring is special. A substring is special when every character inside it appears only within that substring in the original string. The goal is to determine whether at least k such non‑overlapping substrings can be chosen.

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

Generate every possible substring using two nested loops. For each substring, verify whether it is special by checking the first and last occurrence of every character in the substring against the boundaries of the substring. If any character appears outside the range, the substring is invalid. Store all valid substrings and try selecting k non‑overlapping ones using another pass or backtracking. This approach demonstrates the definition clearly but becomes impractical because validating every substring requires scanning characters repeatedly.

Approach 2: Character Interval Expansion + Greedy Selection (O(n log n) time, O(n) space)

First compute the first and last occurrence of every character using a hash table. For each index that represents the first appearance of a character, expand an interval starting at that index and extend it to the farthest last occurrence of all characters encountered while scanning. If expansion ever moves before the starting index of any character, the interval cannot form a valid special substring and is discarded. This produces candidate intervals where all character occurrences are contained inside the interval.

Once valid intervals are collected, treat them like a classic non‑overlapping interval scheduling problem. Sort the intervals by ending index using sorting, then greedily pick intervals whose start is greater than the end of the previously chosen interval. Count how many intervals can be selected. If the count is at least k, the answer is true. The key insight is that minimal valid intervals guarantee character isolation, and greedy earliest‑finish selection maximizes the number of disjoint substrings.

Approach 3: Dynamic Programming on Intervals (O(n log n) time, O(n) space)

Instead of greedy selection, you can sort valid intervals and run a dynamic programming solution similar to weighted interval scheduling. Let dp[i] represent the maximum number of valid substrings that can be chosen considering the first i intervals. For each interval, either include it (and add 1 plus the best compatible interval before it) or skip it. Binary search finds the previous non‑overlapping interval efficiently. This approach is useful if the problem variant later adds weights or additional constraints.

Recommended for interviews: Interval expansion followed by greedy interval scheduling. It runs in near linear time, clearly demonstrates understanding of character boundaries, and uses a classic greedy pattern that interviewers expect. The brute force approach helps explain the definition of a special substring, but the interval + greedy solution shows algorithmic maturity.