Find the original typed string i

String

72.1% acceptance

Feb 23, 2026

524

Alice is attempting to type a specific string on her computer. However, she tends to be clumsy and may press a key for too long, resulting in a character being typed multiple times. Although Alice tried to focus on her typing, she is aware that she may still have done this at most once. You are given a string word, which represents the final output displayed on Alice's screen. Return the total number of possible original strings that Alice might have intended to type.

Solution

Rust

Time O(n²)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn possible_string_count(word: String) -> i32 {
    // At most one key was held too long (one group of consecutive identical chars was extended)
    // Count groups of consecutive identical chars.
    // For each group of length > 1, we can reduce it by 1..group_len-1.
    // Total = 1 (no change) + sum of (group_len - 1) for all groups with len > 1.
    let w = word.as_bytes();
    let n = w.len();
    let mut result = 1i32;
    let mut i = 0;
    while i < n {
      let mut j = i;
      while j < n && w[j] == w[i] { j += 1; }
      let len = (j - i) as i32;
      result += len - 1;
      i = j;
    }
    result
  }
}