Select k disjoint special substrings

Hash Table String Dynamic Programming Greedy Sorting

19.1% acceptance

Feb 25, 2026

142

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.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn max_substring_length(s: String, k: i32) -> bool {
    let k = k as usize;
    let n = s.len();
    let b = s.as_bytes();
    let mut first = [n; 26];
    let mut last = [0usize; 26];
    for (i, &c) in b.iter().enumerate() {
      let ci = (c - b'a') as usize;
      if first[ci] == n { first[ci] = i; }
      last[ci] = i;
    }
    // Enumerate all valid special substrings.
    // Start only from positions that are first occurrences of some char,
    // forward-sweep to find the minimal closed interval, then check validity.
    let mut intervals: Vec<(usize, usize)> = Vec::new();
    for start in 0..n {
      let ci = (b[start] - b'a') as usize;
      if first[ci] != start { continue; }
      let mut hi = last[ci];
      let mut min_first = start;
      let mut j = start;
      while j <= hi {
        let cj = (b[j] - b'a') as usize;
        if last[cj] > hi { hi = last[cj]; }
        if first[cj] < min_first { min_first = first[cj]; }
        j += 1;
      }
      // Valid if no char extends before `start` and not the entire string
      if min_first == start && hi - start + 1 < n {
        intervals.push((hi, start));
      }
    }
    // Greedy interval scheduling: sort by end, pick non-overlapping
    intervals.sort_unstable();
    let mut count = 0usize;
    let mut last_end: i64 = -1;
    for (hi, lo) in intervals {
      if lo as i64 > last_end {
        count += 1;
        last_end = hi as i64;
      }
    }
    count >= k
  }
}