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:
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.
Examples
Example 1
Input: s = "abcdbaefab", k = 2
Output: true
Explanation:
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.
3458. Select K Disjoint Special Substrings
Medium
30 Points
Hash Table
String
Dynamic Programming
Greedy
Sorting
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:
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.
Examples
Example 1
Input: s = "abcdbaefab", k = 2
Output: true
Explanation:
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.
Select K Disjoint Special Substrings - Practice Coding | SlaveCode