3458. Select K Disjoint Special Substrings
Description
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 ins."ef"contains the characters'e'and'f', which do not appear elsewhere ins.
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 * 1040 <= k <= 26sconsists only of lowercase English letters.
Solutions
Solution 1
Thinking
A special substring is the span from a letter's first to last occurrence, and every letter inside must stay inside that span. \(n\le 5\times 10^4\), \(k\le 26\).
Each letter yields at most one candidate interval. Selecting \(k\) disjoint ones is an interval-graph independent set, solvable by sorting right ends.
Compute \([\textit{first},\textit{last}]\) for \(26\) letters, close each interval under contained letters, sort by right end, and greedily pick. Feasible if at least \(k\) intervals are taken.
1 | |
1 | |
1 | |
1 | |