Select K Disjoint Special Substrings

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.

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.

1class Solution {2    public boolean canSelect(String s, int k) {3        if (k == 0) {4            return true;5        }6        int n = s.length();7        int[] first = new int[26];8        int[] last = new int[26];9        java.util.Arrays.fill(first, -1);10        java.util.Arrays.fill(last, -1);11 12        for (int i = 0; i < n; i++) {13            int charIndex = s.charAt(i) - 'a';14            if (first[charIndex] == -1) {15                first[charIndex] = i;16            }17            last[charIndex] = i;18        }19 20        int[] dp = new int[n + 1];21 22        for (int i = 1; i <= n; i++) {23            dp[i] = dp[i - 1];24            int minFirst = n;25            int maxLast = -1;26            for (int j = i - 1; j >= 0; j--) {27                int charIndex = s.charAt(j) - 'a';28                minFirst = Math.min(minFirst, first[charIndex]);29                maxLast = Math.max(maxLast, last[charIndex]);30 31                if (minFirst >= j && maxLast < i) {32                    if (j == 0 && i == n) continue; // Not the entire string33                    dp[i] = Math.max(dp[i], (j > 0 ? dp[j] : 0) + 1);34                }35            }36        }37 38        return dp[n] >= k;39    }40}