Find longest self contained substring

Hash Table String Sorting

58.8% acceptance

Mar 31, 2026

Given a string s, your task is to find the length of the longest self-contained substring of s. A substring t of a string s is called self-contained if t != s and for every character in t, it doesn't exist in the rest of s. Return the length of the longest self-contained substring of s if it exists, otherwise, return -1.

Solution

Rust

Time O(n³)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn max_substring_length(s: String) -> i32 {
    let bytes = s.as_bytes();
    let n = bytes.len();
    let mut first = [n; 26];
    let mut last = [0usize; 26];
    for (i, &b) in bytes.iter().enumerate() {
      let c = (b - b'a') as usize;
      first[c] = first[c].min(i);
      last[c] = last[c].max(i);
    }
    let mut prefix = vec![[0i32; 26]; n + 1];
    for i in 0..n {
      prefix[i + 1] = prefix[i];
      prefix[i + 1][(bytes[i] - b'a') as usize] += 1;
    }
    let mut ans = -1i32;
    for c in 0..26 {
      if first[c] >= n { continue; }
      for d in 0..26 {
        if first[d] >= n { continue; }
        let i = first[c];
        let j = last[d];
        if j < i { continue; }
        if i == 0 && j == n - 1 { continue; }
        let mut valid = true;
        for e in 0..26 {
          if first[e] >= n { continue; }
          let cnt = prefix[j + 1][e] - prefix[i][e];
          if cnt > 0 && (first[e] < i || last[e] > j) {
            valid = false;
            break;
          }
        }
        if valid {
          ans = ans.max((j - i + 1) as i32);
        }
      }
    }
    ans
  }
}