Unique substrings in wraparound string

String Dynamic Programming

42.7% acceptance

Jan 13, 2026

1528

191

We define the string base to be the infinite wraparound string of "abcdefghijklmnopqrstuvwxyz", so base will look like this: "...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd....". Given a string s, return the number of unique non-empty substrings of s are present in base.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn find_substring_in_wrapround_string(s: String) -> i32 {
    use std::collections::HashMap;
    let chars: Vec<char> = s.chars().collect();
    let mut max_len: HashMap<char, i32> = HashMap::new();
    let mut len = 0;
    
    for i in 0..chars.len() {
      if i > 0 && (chars[i] as u8 == chars[i-1] as u8 + 1 || (chars[i-1] == 'z' && chars[i] == 'a')) {
        len += 1;
      } else {
        len = 1;
      }
      max_len.entry(chars[i]).and_modify(|e| *e = (*e).max(len)).or_insert(len);
    }
    
    max_len.values().sum()
  }
}