Maximum number of non overlapping substrings

Hash Table String Greedy Sorting

41.5% acceptance

Feb 25, 2026

883

Given a string s of lowercase letters, you need to find the maximum number of non-empty substrings of s that meet the following conditions: The substrings do not overlap. A substring that contains a certain character c must also contain all occurrences of c. Find the maximum number of substrings that meet the above conditions. If there are multiple solutions with the same number of substrings, return the one with minimum total length.

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn max_num_of_substrings(s: String) -> Vec<String> {
    let bytes = s.as_bytes();
    let _n = bytes.len();
    let mut first = [usize::MAX; 26];
    let mut last = [0usize; 26];
    for (i, &b) in bytes.iter().enumerate() {
      let c = (b - b'a') as usize;
      if first[c] == usize::MAX { first[c] = i; }
      last[c] = i;
    }

    // Compute expanded interval for each char
    let get_interval = |c: usize| -> Option<(usize, usize)> {
      if first[c] == usize::MAX { return None; }
      let mut end = last[c];
      let mut i = first[c];
      while i <= end {
        let d = (bytes[i] - b'a') as usize;
        if first[d] < first[c] { return None; } // c would be absorbed
        end = end.max(last[d]);
        i += 1;
      }
      Some((first[c], end))
    };

    // Collect valid intervals, sort by end
    let mut intervals: Vec<(usize, usize)> = (0..26)
      .filter_map(|c| get_interval(c))
      .collect();
    intervals.sort_by_key(|&(_, e)| e);

    // Greedy: pick non-overlapping intervals
    let mut result = Vec::new();
    let mut prev_end: i64 = -1;
    for (l, r) in intervals {
      if l as i64 > prev_end {
        result.push(s[l..=r].to_string());
        prev_end = r as i64;
      }
    }
    result
  }
}