Split message based on limit

String Enumeration

42.0% acceptance

Feb 25, 2026

198

201

You are given a string, message, and a positive integer, limit. You must split message into one or more parts based on limit. Each resulting part should have the suffix "", where "b" is the total number of parts and "a" is the index of the part (1-based). The length of each resulting part (including its suffix) should be equal to limit, except for the last part whose length can be at most limit. Return the parts message would be split into as an array of strings. If impossible, return an empty array.

Solution

Rust

Time O(log n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn split_message(message: String, limit: i32) -> Vec<String> {
    fn num_len(mut x: usize) -> usize {
      if x == 0 { return 1; }
      let mut d = 0;
      while x > 0 { d += 1; x /= 10; }
      d
    }
    // Capacity for b parts in O(log b): group indices by digit count of a.
    // NOTE: capacity is NOT globally monotone — it drops when db increases,
    // so we must scan linearly and stop at the first b where cap >= n.
    fn capacity(b: usize, limit: usize) -> usize {
      if b == 0 { return 0; }
      let db = num_len(b);
      let mut cap = 0usize;
      let mut start = 1usize;
      let mut da = 1usize;
      while start <= b {
        let end = (10usize.pow(da as u32) - 1).min(b);
        let count = end - start + 1;
        let suffix = 3 + da + db;
        if limit > suffix {
          cap = cap.saturating_add(count * (limit - suffix));
        }
        start = end + 1;
        da += 1;
      }
      cap
    }

    let msg = message.as_bytes();
    let n = msg.len();
    let limit = limit as usize;

    // Scan b from 1 upward; use an O(log b) per-step incremental running sum.
    // When db stays the same, just add the new part's contribution.
    // When db grows, recompute from scratch (only happens O(log n) times total).
    let mut b = 0usize;
    let mut cap = 0usize;
    let mut db = 0usize;
    loop {
      b += 1;
      let new_db = num_len(b);
      if new_db != db {
        // db changed — recompute cap with the updated db in O(log b)
        db = new_db;
        cap = capacity(b, limit);
      } else {
        // Fast incremental update: just add contribution of the new b-th part
        let da = num_len(b);
        let suffix = 3 + da + db;
        if limit > suffix {
          cap = cap.saturating_add(limit - suffix);
        }
      }
      if cap >= n { break; }
      // Each valid part carries ≥ 1 char, so b can never exceed n for a solvable input.
      if b >= n { return vec![]; }
    }

    // Build result
    let db = num_len(b);
    let mut result = Vec::with_capacity(b);
    let mut idx = 0;
    for a in 1..=b {
      let da = num_len(a);
      let suffix_len = 3 + da + db;
      if limit <= suffix_len { return vec![]; }
      let take = (limit - suffix_len).min(n - idx);
      if take == 0 { return vec![]; }
      let content = std::str::from_utf8(&msg[idx..idx + take]).unwrap();
      result.push(format!("{}<{}/{}>", content, a, b));
      idx += take;
    }
    result
  }
}