Swap for longest repeated character substring

Hash Table String Sliding Window

44.2% acceptance

Feb 25, 2026

1079

104

You are given a string text. You can swap two of the characters in the text. Return the length of the longest substring with repeated characters.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn max_rep_opt1(text: String) -> i32 {
    let s: Vec<u8> = text.bytes().collect();
    let n = s.len();
    // Count total occurrences of each character
    let mut total = [0i32; 26];
    for &c in &s { total[(c - b'a') as usize] += 1; }
    // Find runs
    let mut runs: Vec<(u8, i32)> = Vec::new(); // (char, length)
    let mut i = 0;
    while i < n {
      let c = s[i];
      let mut j = i;
      while j < n && s[j] == c { j += 1; }
      runs.push((c, (j - i) as i32));
      i = j;
    }
    let mut ans = 0;
    let nr = runs.len();
    for k in 0..nr {
      let (c, len) = runs[k];
      let ci = (c - b'a') as usize;
      // Case 1: just this run + 1 extra swap from elsewhere (if available)
      let extra = if total[ci] > len { 1 } else { 0 };
      ans = ans.max(len + extra);
      // Case 2: merge with next run if separated by single char
      if k + 2 < nr && runs[k+1].1 == 1 && runs[k+2].0 == c {
        let merged = len + runs[k+2].1;
        let has_extra = if total[ci] > merged { 1 } else { 0 };
        ans = ans.max(merged + has_extra);
      }
    }
    ans
  }
}