Good indices in a digit string

Math String

88.2% acceptance

Apr 3, 2026

You are given a string s consisting of digits. An index i is called good if there exists a substring of s that ends at index i and is equal to the decimal representation of i. Return an integer array of all good indices in increasing order.

Solution

Rust

Time O(2^n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn good_indices(s: String) -> Vec<i32> {
    let bytes = s.as_bytes();
    let mut answer = Vec::new();

    for index in 0..bytes.len() {
      if Self::matches_index(bytes, index) {
        answer.push(index as i32);
      }
    }

    answer
  }

  fn matches_index(bytes: &[u8], index: usize) -> bool {
    let mut value = index;
    let mut digits = [0u8; 6];
    let mut len = 0usize;

    loop {
      digits[len] = b'0' + (value % 10) as u8;
      len += 1;
      value /= 10;
      if value == 0 {
        break;
      }
    }

    if len > index + 1 {
      return false;
    }

    for offset in 0..len {
      if bytes[index - offset] != digits[offset] {
        return false;
      }
    }

    true
  }
}