Lexicographically smallest permutation greater than target

Hash Table String Greedy Counting Enumeration

26.5% acceptance

Feb 24, 2026

113

You are given two strings s and target, both having length n, consisting of lowercase English letters. Return the lexicographically smallest permutation of s that is strictly greater than target. If no permutation of s is lexicographically strictly greater than target, return an empty string.

Solution

Rust

Time O(n³)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn lex_greater_permutation(s: String, target: String) -> String {
    let n = s.len();
    let s: Vec<u8> = s.bytes().collect();
    let t: Vec<u8> = target.bytes().collect();
    let mut freq = [0i32; 26];
    for &c in &s { freq[(c - b'a') as usize] += 1; }

    // Try to build the lexicographically smallest permutation > target
    // Greedy: fix prefix that matches target, then at some position use a char > t[i]
    // with remaining chars sorted ascending
    let mut result = Vec::with_capacity(n);

    fn smallest_greater(
      pos: usize,
      n: usize,
      t: &[u8],
      freq: &mut [i32; 26],
      result: &mut Vec<u8>,
    ) -> bool {
      if pos == n {
        return false; // equal, not strictly greater
      }
      // Try to place t[pos] and recurse
      let tc = (t[pos] - b'a') as usize;
      if freq[tc] > 0 {
        freq[tc] -= 1;
        result.push(t[pos]);
        if smallest_greater(pos + 1, n, t, freq, result) {
          return true;
        }
        result.pop();
        freq[tc] += 1;
      }
      // Try to place a char strictly greater than t[pos], then fill remaining ascending
      for c in (tc + 1)..26 {
        if freq[c] > 0 {
          freq[c] -= 1;
          result.push(b'a' + c as u8);
          // Fill remaining in ascending order
          for cc in 0..26 {
            for _ in 0..freq[cc] {
              result.push(b'a' + cc as u8);
            }
          }
          return true;
        }
      }
      false
    }

    let mut freq_copy = freq;
    if smallest_greater(0, n, &t, &mut freq_copy, &mut result) {
      String::from_utf8(result).unwrap()
    } else {
      String::new()
    }
  }
}