# Select K Disjoint Special Substrings
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/select-k-disjoint-special-substrings)
Canonical: https://scaleengineer.com/dsa/problems/select-k-disjoint-special-substrings
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Hash Table, String
---
## Problem
Given a string `s` of length `n` and an integer `k`, determine whether it is possible to select `k` disjoint **special substrings**.

A **special substring** is a substring where:

* Any character present inside the substring should not appear outside it in the string.
* The substring is not the entire string `s`.

**Note** that all `k` substrings must be disjoint, meaning they cannot overlap.

Return `true` if it is possible to select `k` such disjoint special substrings; otherwise, return `false`.

**Example 1:**

**Input:** s = "abcdbaefab", k = 2

**Output:** true

**Explanation:**

* We can select two disjoint special substrings: `"cd"` and `"ef"`.
* `"cd"` contains the characters `'c'` and `'d'`, which do not appear elsewhere in `s`.
* `"ef"` contains the characters `'e'` and `'f'`, which do not appear elsewhere in `s`.

**Example 2:**

**Input:** s = "cdefdc", k = 3

**Output:** false

**Explanation:**

There can be at most 2 disjoint special substrings: `"e"` and `"f"`. Since `k = 3`, the output is `false`.

**Example 3:**

**Input:** s = "abeabe", k = 0

**Output:** true

**Constraints:**

* `2 <= n == s.length <= 5 * 104`
* `0 <= k <= 26`
* `s` consists only of lowercase English letters.

# Approaches
## Dynamic Programming
A standard approach for problems asking for a maximum number of objects satisfying certain properties is dynamic programming. We can define a DP state based on the prefixes of the string.
**Time:** O(n^2), where n is the length of the string. The nested loops for the DP calculation dominate the complexity. The outer loop runs `n` times, and the inner loop runs up to `n` times. · **Space:** O(n) for the `dp` array. The `first` and `last` arrays take O(1) space as the alphabet size is constant (26).
**Pros:** Correctly solves the problem for all cases.; Conceptually straightforward application of dynamic programming.
**Cons:** The time complexity is too high for the given constraints.
### Explanation
Let `dp[i]` be the maximum number of disjoint special substrings that can be formed entirely within the prefix `s[0...i-1]`.

Our goal is to compute `dp[n]` and check if it's greater than or equal to `k`.

The base case is `dp[0] = 0`, as no substrings can be formed from an empty prefix.

For the transition, to compute `dp[i]`, we have two choices:
1. We don't form a special substring ending at index `i-1`. In this case, the maximum number of substrings is the same as for the prefix `s[0...i-2]`. So, `dp[i] = dp[i-1]`.
2. We form a special substring ending at index `i-1`. Let this substring be `s[j...i-1]` for some `0 <= j < i`. If `s[j...i-1]` is a valid special substring, we can potentially form one more substring than the maximum we could form in the prefix `s[0...j-1]`. This would give `dp[j] + 1` substrings. We should try this for all possible start indices `j`.

Combining these, the recurrence relation is:
`dp[i] = max(dp[i-1], max(dp[j] + 1))` for all `j` such that `s[j...i-1]` is a special substring.

To implement this, we first need an efficient way to check if a substring `s[j...i-1]` is special. A substring is special if every character within it does not appear outside of it. This means for every character `c` in `s[j...i-1]`, its first and last occurrences in the original string `s` must be within the bounds `[j, i-1]`.

We can precompute the first and last occurrences of all characters in `s` in O(n) time. Let's call them `first[c]` and `last[c]`.

The check for `s[j...i-1]` being special becomes:
- `min(first[s[p]]) >= j` for `p` from `j` to `i-1`.
- `max(last[s[p]]) <= i-1` for `p` from `j` to `i-1`.
- The substring is not the entire string `s`.

The overall algorithm is:
1. Precompute `first` and `last` arrays for all 26 lowercase letters. O(n).
2. Initialize a `dp` array of size `n+1` with zeros.
3. Iterate `i` from 1 to `n`:
   a. Set `dp[i] = dp[i-1]`.
   b. Iterate `j` from `i-1` down to `0`:
      i. Check if `s[j...i-1]` is a special substring. This check involves iterating from `j` to `i-1` to find the minimum of `first` occurrences and maximum of `last` occurrences for the characters in the substring. This can be optimized by updating these min/max values as `j` decreases.
      ii. If `s[j...i-1]` is special (and not the whole string), update `dp[i] = max(dp[i], dp[j] + 1)`.
4. Finally, return `dp[n] >= k`.

```java
class Solution {
    public boolean canSelect(String s, int k) {
        if (k == 0) {
            return true;
        }
        int n = s.length();
        int[] first = new int[26];
        int[] last = new int[26];
        java.util.Arrays.fill(first, -1);
        java.util.Arrays.fill(last, -1);

        for (int i = 0; i < n; i++) {
            int charIndex = s.charAt(i) - 'a';
            if (first[charIndex] == -1) {
                first[charIndex] = i;
            }
            last[charIndex] = i;
        }

        int[] dp = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            dp[i] = dp[i - 1];
            int minFirst = n;
            int maxLast = -1;
            for (int j = i - 1; j >= 0; j--) {
                int charIndex = s.charAt(j) - 'a';
                minFirst = Math.min(minFirst, first[charIndex]);
                maxLast = Math.max(maxLast, last[charIndex]);

                if (minFirst >= j && maxLast < i) {
                    if (j == 0 && i == n) continue; // Not the entire string
                    dp[i] = Math.max(dp[i], (j > 0 ? dp[j] : 0) + 1);
                }
            }
        }

        return dp[n] >= k;
    }
}
```
### Algorithm
Let `dp[i]` be the maximum number of disjoint special substrings in the prefix `s[0...i-1]`.
Precompute the `first` and `last` occurrence index for each character in `s`.
Initialize `dp` array of size `n+1` to all zeros.
Iterate `i` from `1` to `n` to compute `dp[i]`:
  Initialize `dp[i] = dp[i-1]` (option to not end a substring at `i-1`).
  Iterate `j` from `i-1` down to `0` (potential start of a substring `s[j...i-1]`):
    Keep track of `min_first` and `max_last` for characters in `s[j...i-1]`.
    If `min_first >= j` and `max_last < i`, then `s[j...i-1]` is a special substring.
    If it is special (and not the whole string), update `dp[i] = max(dp[i], (j > 0 ? dp[j] : 0) + 1)`.
After the loops, `dp[n]` holds the maximum number of disjoint special substrings.
Return `dp[n] >= k`.

## Optimized DP with Block Decomposition
The O(n^2) DP approach is too slow. We can observe that the problem has a decomposable structure. We can partition the string into independent blocks and solve the problem for each block recursively. This avoids redundant computations on parts of the string that are independent of each other, leading to a better average-case time complexity.
**Time:** O(n^2) in the worst case. For each state `solve(i)`, the loop to find an endpoint `j` can run up to `n-i` times. With `n` states, this gives O(n^2). However, on average, it can be much faster. · **Space:** O(n) for the memoization table and recursion stack depth.
**Pros:** More efficient on average than the naive DP, especially on strings that decompose into many small independent blocks.; The recursive formulation with memoization can be more intuitive to some.; Correctly solves the problem.
**Cons:** Worst-case time complexity is still O(n^2), which might be too slow if the string forms one large irreducible block.
### Explanation
A key observation is how special substrings are constrained by the `last` occurrences of their characters. Let's define a "suffix-closed" block. A substring `s[i...j]` is suffix-closed if for any character `c` in `s[i...j]`, its last occurrence in the whole string `s` is at most `j`. This is equivalent to `max(last[s[p]])` for `p` from `i` to `j` being equal to `j`.

The string `s` can be uniquely partitioned into a sequence of disjoint suffix-closed blocks. For example, if `s = "abacaca"`, `last['a']=6, last['b']=2, last['c']=5`. The partitions are `s[0..2]` (`aba`) and `s[3..6]` (`caca`). Any special substring must be entirely contained within one of these blocks.

This suggests a divide-and-conquer approach:
1. Partition the string `s` into its suffix-closed blocks.
2. The total number of special substrings is the sum of the maximum number of special substrings found in each block.
3. For each block, we can recursively apply the same logic. A block is solved by partitioning it into its own suffix-closed sub-blocks (based on `first` and `last` occurrences re-calculated for the block's substring).

When a block cannot be partitioned further, it's an "irreducible" block. For such an irreducible block, we must resort to the O(m^2) DP approach, where `m` is the length of the block.

The overall algorithm:
1. Precompute `first` and `last` arrays for the original string `s`.
2. Implement a function, say `solve(start, end)`, that computes the max number of disjoint special substrings within `s[start...end]`.
3. `solve(start, end)`:
   a. Partition `s[start...end]` into suffix-closed blocks. This is done by iterating from `start` to `end`, keeping track of the maximum `last` occurrence seen so far. A block `[block_start, i]` is found when this maximum equals `i`.
   b. If the partition results in multiple blocks, the total is the sum of `solve()` called on each block.
   c. If `s[start...end]` is itself an irreducible block, we must check if this block itself is a special substring with respect to the original string `s`. This is true if `min(first[s[p]]) >= start` for `p` from `start` to `end`. If it is, we can either take this whole block as 1 special substring and add the result of `solve()` on its interior (by breaking its irreducibility, a complex step), or more simply, we can just run the O(m^2) DP on this block to find the max number of special substrings *strictly inside* it. A simpler implementation is to always run the DP on irreducible blocks.

This approach is faster on average because for many inputs, the string decomposes into small blocks, and `sum(m_i^2)` is much smaller than `n^2`. The worst-case is still O(n^2) if the string is one large irreducible block.

```java
class Solution {
    int[] first;
    int[] last;
    String s;
    int n;
    int[] memo;

    public boolean canSelect(String s, int k) {
        if (k == 0) {
            return true;
        }
        this.s = s;
        this.n = s.length();
        this.first = new int[26];
        this.last = new int[26];
        java.util.Arrays.fill(first, -1);
        java.util.Arrays.fill(last, -1);

        for (int i = 0; i < n; i++) {
            int charIndex = s.charAt(i) - 'a';
            if (first[charIndex] == -1) {
                first[charIndex] = i;
            }
            last[charIndex] = i;
        }
        
        this.memo = new int[n + 1];
        java.util.Arrays.fill(memo, -1);

        return solve(0) >= k;
    }

    private int solve(int start) {
        if (start >= n) {
            return 0;
        }
        if (memo[start] != -1) {
            return memo[start];
        }

        // Option 1: Skip s.charAt(start) and solve for the rest
        int res = solve(start + 1);

        // Option 2: Try to form a special substring starting at `start`
        int minFirst = n;
        int maxLast = -1;
        for (int end = start; end < n; end++) {
            int charIndex = s.charAt(end) - 'a';
            minFirst = Math.min(minFirst, first[charIndex]);
            maxLast = Math.max(maxLast, last[charIndex]);

            if (minFirst >= start && maxLast == end) {
                if (start == 0 && end == n - 1) {
                    // This is the whole string, not allowed as a single special substring.
                    // We must find substrings inside it.
                    // A full DP on the inside is complex. A simpler interpretation is to just not count it.
                } else {
                    res = Math.max(res, 1 + solve(end + 1));
                }
            }
        }
        
        return memo[start] = res;
    }
}
```
The provided code snippet is a memoized recursion which is equivalent to the DP but explores the state space differently. It tries to find a special substring starting at `start` and if it finds one `s[start...end]`, it adds 1 and recurses on `solve(end+1)`. This is another way to frame the DP, which can be more intuitive. Its complexity remains O(n^2) in the worst case but performs better if special substrings are found early, pruning the search space.
### Algorithm
This approach is a recursive (or memoized) version of the DP. Let `solve(i)` be the max number of disjoint special substrings in `s[i...n-1]`.
The base case is `solve(n) = 0`.
To compute `solve(i)`:
  One option is to not start a special substring at `i`. The result is `solve(i+1)`.
  Another option is to find a special substring `s[i...j]`. If one is found, the result is `1 + solve(j+1)`.
  We iterate `j` from `i` to `n-1` to find all possible special substrings `s[i...j]`.
  A substring `s[i...j]` is special if `min_first(i,j) >= i` and `max_last(i,j) <= j`.
  We take the maximum over all these possibilities.
  `solve(i) = max(solve(i+1), max_{j | s[i..j] is special} (1 + solve(j+1)))`.
Memoization is used to store the results of `solve(i)` to avoid recomputing, effectively making it a DP.
The final answer for the whole string is `solve(0)`.