Select K Disjoint Special Substrings

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.

Examples

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 * 10^4
• 0 <= k <= 26
• s consists only of lowercase English letters.

Solution

Method 1 - Greedy Interval Selection

Intuition

We want to find the maximum number of disjoint substrings where all characters in each substring are unique to that substring (do not appear elsewhere in the string). This is equivalent to finding the maximum number of disjoint intervals, where each interval covers all occurrences of its characters. We can use a greedy approach similar to the "Partition Labels" problem, but we must ensure substrings are not the entire string.

Approach

1. For each character, record its first and last occurrence.
2. For each position, expand the current interval to cover all last occurrences of characters seen so far.
3. When the current position reaches the end of the interval, check if the interval is not the entire string, and add it as a special substring.
4. Count the number of such disjoint special substrings. Return true if the count is at least k.

Code

C++

#include <vector>
#include <string>
using namespace std;
class Solution {
public:
    bool canSelectKDisjointSpecialSubstrings(string s, int k) {
        int n = s.size();
        vector<int> first(26, n), last(26, -1);
        for (int i = 0; i < n; ++i) {
            int c = s[i] - 'a';
            first[c] = min(first[c], i);
            last[c] = max(last[c], i);
        }
        int count = 0, i = 0;
        while (i < n) {
            int l = i, r = last[s[i]-'a'];
            for (int j = l; j <= r; ++j)
                r = max(r, last[s[j]-'a']);
            if (l == 0 && r == n-1) { i = r+1; continue; } // skip whole string
            count++;
            i = r+1;
        }
        return k == 0 || count >= k;
    }
};

Go

func canSelectKDisjointSpecialSubstrings(s string, k int) bool {
    n := len(s)
    first := make([]int, 26)
    last := make([]int, 26)
    for i := range first { first[i] = n; last[i] = -1 }
    for i, c := range s {
        idx := int(c - 'a')
        if i < first[idx] { first[idx] = i }
        if i > last[idx] { last[idx] = i }
    }
    count, i := 0, 0
    for i < n {
        l, r := i, last[s[i]-'a']
        for j := l; j <= r; j++ {
            if last[s[j]-'a'] > r { r = last[s[j]-'a'] }
        }
        if l == 0 && r == n-1 { i = r+1; continue }
        count++
        i = r+1
    }
    return k == 0 || count >= k
}

Java

class Solution {
    public boolean canSelectKDisjointSpecialSubstrings(String s, int k) {
        int n = s.length();
        int[] first = new int[26], last = new int[26];
        for (int i = 0; i < 26; ++i) { first[i] = n; last[i] = -1; }
        for (int i = 0; i < n; ++i) {
            int c = s.charAt(i) - 'a';
            first[c] = Math.min(first[c], i);
            last[c] = Math.max(last[c], i);
        }
        int count = 0, i = 0;
        while (i < n) {
            int l = i, r = last[s.charAt(i)-'a'];
            for (int j = l; j <= r; ++j)
                r = Math.max(r, last[s.charAt(j)-'a']);
            if (l == 0 && r == n-1) { i = r+1; continue; }
            count++;
            i = r+1;
        }
        return k == 0 || count >= k;
    }
}

Kotlin

class Solution {
    fun canSelectKDisjointSpecialSubstrings(s: String, k: Int): Boolean {
        val n = s.length
        val first = IntArray(26) { n }
        val last = IntArray(26) { -1 }
        for (i in s.indices) {
            val c = s[i] - 'a'
            first[c] = minOf(first[c], i)
            last[c] = maxOf(last[c], i)
        }
        var count = 0
        var i = 0
        while (i < n) {
            var l = i
            var r = last[s[i] - 'a']
            var j = l
            while (j <= r) {
                r = maxOf(r, last[s[j] - 'a'])
                j++
            }
            if (l == 0 && r == n-1) { i = r+1; continue }
            count++
            i = r+1
        }
        return k == 0 || count >= k
    }
}

Python

def canSelectKDisjointSpecialSubstrings(s: str, k: int) -> bool:
    n = len(s)
    first = [n]*26
    last = [-1]*26
    for i, c in enumerate(s):
        idx = ord(c) - ord('a')
        first[idx] = min(first[idx], i)
        last[idx] = max(last[idx], i)
    count = 0
    i = 0
    while i < n:
        l = i
        r = last[ord(s[i])-ord('a')]
        j = l
        while j <= r:
            r = max(r, last[ord(s[j])-ord('a')])
            j += 1
        if l == 0 and r == n-1:
            i = r+1
            continue
        count += 1
        i = r+1
    return k == 0 or count >= k

Rust

pub fn can_select_k_disjoint_special_substrings(s: &str, k: i32) -> bool {
    let n = s.len();
    let s = s.as_bytes();
    let mut first = vec![n; 26];
    let mut last = vec![-1; 26];
    for (i, &c) in s.iter().enumerate() {
        let idx = (c - b'a') as usize;
        if i < first[idx] { first[idx] = i; }
        if i as i32 > last[idx] { last[idx] = i as i32; }
    }
    let mut count = 0;
    let mut i = 0;
    while i < n {
        let l = i;
        let mut r = last[(s[i] - b'a') as usize] as usize;
        let mut j = l;
        while j <= r {
            r = r.max(last[(s[j] - b'a') as usize] as usize);
            j += 1;
        }
        if l == 0 && r == n-1 { i = r+1; continue; }
        count += 1;
        i = r+1;
    }
    k == 0 || count >= k
}

TypeScript

function canSelectKDisjointSpecialSubstrings(s: string, k: number): boolean {
    const n = s.length;
    const first = Array(26).fill(n);
    const last = Array(26).fill(-1);
    for (let i = 0; i < n; ++i) {
        const idx = s.charCodeAt(i) - 97;
        first[idx] = Math.min(first[idx], i);
        last[idx] = Math.max(last[idx], i);
    }
    let count = 0, i = 0;
    while (i < n) {
        let l = i, r = last[s.charCodeAt(i)-97];
        for (let j = l; j <= r; ++j)
            r = Math.max(r, last[s.charCodeAt(j)-97]);
        if (l === 0 && r === n-1) { i = r+1; continue; }
        count++;
        i = r+1;
    }
    return k === 0 || count >= k;
}

Complexity

• ⏰ Time complexity: O(n) (single pass, n = length of s)
• 🧺 Space complexity: O(1) (since alphabet size is constant)