Splitting a string into descending consecutive values

String Backtracking Enumeration

37.4% acceptance

Feb 25, 2026

551

128

You are given a string s that consists of only digits. Check if we can split s into two or more non-empty substrings such that the numerical values of the substrings are in descending order and the difference between numerical values of every two adjacent substrings is equal to 1.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn split_string(s: String) -> bool {
    let bytes = s.as_bytes();

    fn dfs(b: &[u8], idx: usize, count: usize, prev: Option<u64>) -> bool {
      if idx == b.len() {
        return count >= 2;
      }
      let mut val: u64 = 0;
      for j in idx..b.len() {
        // checked mul and add to avoid overflow
        val = match val.checked_mul(10).and_then(|v| v.checked_add((b[j] - b'0') as u64)) {
          Some(v) => v,
          None => return false, // overflow means too large
        };
        if let Some(p) = prev {
          if p == 0 {
            return false; // p-1 would underflow
          }
          if val == p - 1 {
            if dfs(b, j + 1, count + 1, Some(val)) {
              return true;
            }
          }
          if val >= p {
            break; // val can only grow, no point continuing
          }
        } else {
          // first number, try all prefixes
          if dfs(b, j + 1, count + 1, Some(val)) {
            return true;
          }
        }
      }
      false
    }

    dfs(bytes, 0, 0, None)
  }
}