Lexicographically smallest string after reverse ii

String Binary Search Rolling Hash Suffix Array Hash Function

45.5% acceptance

Mar 31, 2026

You are given a string s of length n consisting of lowercase English letters. You must perform exactly one operation by choosing any integer k such that 1 <= k <= n and either: reverse the first k characters of s, or reverse the last k characters of s. Return the lexicographically smallest string that can be obtained after exactly one such operation.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn lex_smallest(s: String) -> String {
    let bytes = s.as_bytes();
    let n = bytes.len();

    const BASE: u64 = 131;
    const MOD1: u64 = 1_000_000_007;
    const MOD2: u64 = 998_244_353;

    let mut pow1 = vec![1u64; n + 1];
    let mut pow2 = vec![1u64; n + 1];
    for i in 1..=n {
      pow1[i] = pow1[i - 1] * BASE % MOD1;
      pow2[i] = pow2[i - 1] * BASE % MOD2;
    }

    // Forward hash: fh1[i] = hash(s[0..i])
    let mut fh1 = vec![0u64; n + 1];
    let mut fh2 = vec![0u64; n + 1];
    for i in 0..n {
      fh1[i + 1] = (fh1[i] * BASE + bytes[i] as u64) % MOD1;
      fh2[i + 1] = (fh2[i] * BASE + bytes[i] as u64) % MOD2;
    }

    // Reverse hash: rh_[i] = hash(rev_s[0..i]) where rev_s[j] = bytes[n-1-j]
    let mut rh1 = vec![0u64; n + 1];
    let mut rh2 = vec![0u64; n + 1];
    for i in 0..n {
      rh1[i + 1] = (rh1[i] * BASE + bytes[n - 1 - i] as u64) % MOD1;
      rh2[i + 1] = (rh2[i] * BASE + bytes[n - 1 - i] as u64) % MOD2;
    }

    // Hash of s[l..r]
    let fh = |l: usize, r: usize| -> (u64, u64) {
      (
        (fh1[r] + MOD1 - fh1[l] * pow1[r - l] % MOD1) % MOD1,
        (fh2[r] + MOD2 - fh2[l] * pow2[r - l] % MOD2) % MOD2,
      )
    };

    // Hash of rev_s[l..r]
    let rh = |l: usize, r: usize| -> (u64, u64) {
      (
        (rh1[r] + MOD1 - rh1[l] * pow1[r - l] % MOD1) % MOD1,
        (rh2[r] + MOD2 - rh2[l] * pow2[r - l] % MOD2) % MOD2,
      )
    };

    // Hash of result[l..r] for candidate (is_prefix, k)
    // Prefix k: result[i] = bytes[k-1-i] = rev_s[n-k+i] for i<k; bytes[i] for i>=k
    // Suffix k: result[i] = bytes[i] for i<n-k; rev_s[i-(n-k)] for i>=n-k
    let seg_hash = |is_prefix: bool, k: usize, l: usize, r: usize| -> (u64, u64) {
      if is_prefix {
        if r <= k {
          rh(n - k + l, n - k + r)
        } else if l >= k {
          fh(l, r)
        } else {
          let (h1l, h2l) = rh(n - k + l, n);
          let (h1r, h2r) = fh(k, r);
          let rlen = r - k;
          ((h1l * pow1[rlen] + h1r) % MOD1, (h2l * pow2[rlen] + h2r) % MOD2)
        }
      } else {
        let split = n - k;
        if r <= split {
          fh(l, r)
        } else if l >= split {
          rh(l - split, r - split)
        } else {
          let (h1l, h2l) = fh(l, split);
          let (h1r, h2r) = rh(0, r - split);
          let rlen = r - split;
          ((h1l * pow1[rlen] + h1r) % MOD1, (h2l * pow2[rlen] + h2r) % MOD2)
        }
      }
    };

    let get_char = |is_prefix: bool, k: usize, i: usize| -> u8 {
      if is_prefix {
        if i < k { bytes[k - 1 - i] } else { bytes[i] }
      } else {
        if i < n - k { bytes[i] } else { bytes[n - 1 - (i - (n - k))] }
      }
    };

    // Binary search for LCP length of two candidates — O(log n) per call
    let lcp = |p1: bool, k1: usize, p2: bool, k2: usize| -> usize {
      let mut lo = 0usize;
      let mut hi = n;
      while lo < hi {
        let mid = (lo + hi + 1) / 2;
        if seg_hash(p1, k1, 0, mid) == seg_hash(p2, k2, 0, mid) {
          lo = mid;
        } else {
          hi = mid - 1;
        }
      }
      lo
    };

    let is_better = |p1: bool, k1: usize, p2: bool, k2: usize| -> bool {
      let l = lcp(p1, k1, p2, k2);
      l < n && get_char(p1, k1, l) < get_char(p2, k2, l)
    };

    let mut bp = true;
    let mut bk = 1usize;

    for prefix in [true, false] {
      for k in 2..=n {
        if is_better(prefix, k, bp, bk) {
          bp = prefix;
          bk = k;
        }
      }
    }

    let mut result = Vec::with_capacity(n);
    for i in 0..n {
      result.push(get_char(bp, bk, i));
    }
    String::from_utf8(result).unwrap()
  }
}