Substring with concatenation of all words

Hash Table String Sliding Window

34.0% acceptance

Jan 12, 2026

2607

430

You are given a string s and an array of strings words. All the strings of words are of the same length. A concatenated string is a string that exactly contains all the strings of any permutation of words concatenated. For example, if words = ["ab","cd","ef"], then "abcdef", "abefcd", "cdabef", "cdefab", "efabcd", and "efcdab" are all concatenated strings. "acdbef" is not a concatenated string because it is not the concatenation of any permutation of words. Return an array of the starting indices of all the concatenated substrings in s. You can return the answer in any order.

Solution

Rust

Time O(n³)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn find_substring(s: String, words: Vec<String>) -> Vec<i32> {
    use std::collections::HashMap;
    
    if words.is_empty() {
      return vec![];
    }
    
    let word_len = words[0].len();
    let num_words = words.len();
    let s_len = s.len();
    
    if s_len < word_len * num_words {
      return vec![];
    }
    
    let s_bytes = s.as_bytes();
    
    // Map words to indices
    let mut word_to_id: HashMap<&str, usize> = HashMap::new();
    let mut word_count: Vec<usize> = Vec::new();
    
    for word in &words {
      let id = word_to_id.len();
      let word_id = *word_to_id.entry(word.as_str()).or_insert(id);
      if word_id == word_count.len() {
        word_count.push(0);
      }
      word_count[word_id] += 1;
    }
    
    let num_unique = word_count.len();
    let mut result = Vec::new();
    
    for offset in 0..word_len.min(s_len) {
      if offset + word_len > s_len {
        break;
      }
      
      let mut seen = vec![0usize; num_unique];
      let mut count = 0;
      let mut left = offset;
      let mut right = offset;
      
      while right + word_len <= s_len {
        let word = unsafe { std::str::from_utf8_unchecked(&s_bytes[right..right + word_len]) };
        right += word_len;
        
        if let Some(&id) = word_to_id.get(word) {
          seen[id] += 1;
          count += 1;
          
          while seen[id] > word_count[id] {
            let left_word = unsafe { std::str::from_utf8_unchecked(&s_bytes[left..left + word_len]) };
            let left_id = word_to_id[left_word];
            seen[left_id] -= 1;
            left += word_len;
            count -= 1;
          }
          
          if count == num_words {
            result.push(left as i32);
            let left_word = unsafe { std::str::from_utf8_unchecked(&s_bytes[left..left + word_len]) };
            let left_id = word_to_id[left_word];
            seen[left_id] -= 1;
            left += word_len;
            count -= 1;
          }
        } else {
          for x in seen.iter_mut() {
            *x = 0;
          }
          count = 0;
          left = right;
        }
      }
    }
    
    result.sort_unstable();
    result
  }
}