Find maximum number of non intersecting substrings

Hash Table String Dynamic Programming Greedy

30.5% acceptance

Feb 25, 2026

You are given a string word. Return the maximum number of non-intersecting substrings of word that are at least four characters long and start and end with the same letter.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn max_substrings(word: String) -> i32 {
    // Earliest-end greedy: scan end positions j left to right.
    // At each j, check if there is any occurrence of bytes[j] in [current_start, j-3].
    // If yes, take this substring (it has the earliest possible end), count++,
    // advance current_start to j+1.
    // This is equivalent to the interval-scheduling "earliest deadline first" strategy.

    let bytes = word.as_bytes();
    let n = bytes.len();

    // For each char c, store sorted list of positions.
    let mut positions: Vec<Vec<usize>> = vec![vec![]; 26];
    for (i, &b) in bytes.iter().enumerate() {
      positions[(b - b'a') as usize].push(i);
    }

    let mut count = 0;
    let mut current_start = 0usize;

    for j in 3..n {
      let c = (bytes[j] - b'a') as usize;
      let pos = &positions[c];
      // Find the first occurrence of c that is >= current_start.
      let lo = pos.partition_point(|&x| x < current_start);
      // Valid if that occurrence is also <= j-3 (substring length >= 4).
      if lo < pos.len() && pos[lo] <= j - 3 {
        count += 1;
        current_start = j + 1;
      }
    }

    count
  }
}