LeetCode Entry

3720. Lexicographically Smallest Permutation Greater Than Target

27.08.2026 medium 2026 kotlin rust

Smallest permutation bigger than target

3720. Lexicographically Smallest Permutation Greater Than Target medium substack youtube

https://dmitrysamoylenko.com/leetcode/

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1464

Problem TLDR

Smallest permutation bigger than target

Intuition

Try to one-up every position. The tail is just sorted remainder.

Approach

• to match the prefix adjust the frequency; exit at the first mismatch

Complexity

• Time complexity: \(O(n^2)\)

• Space complexity: \(O(1)\)

Code

    fun lexGreaterPermutation(s: String, t: String): String {
        val f = IntArray(128); for (c in s) ++f[c.code]; var r = ""
        for (i in t.indices) {
            (t[i] + 1..'z').find { f[it.code] > 0 }?.run {
                f[code]--
                r = t.take(i) + this + ('a'..'z').joinToString("") { "$it".repeat(f[it.code]) }
                f[code]++
            }
            if (f[t[i].code]-- == 0) break
        };   return r
    }

    pub fn lex_greater_permutation(s: String, t: String) -> String {
        let (mut f, mut r) = ([0; 123], "".into()); for b in s.bytes() { f[b as usize] += 1 }
        for (i, b) in t.bytes().enumerate() {
            if let Some(c) = (b + 1..=122).find(|&c| f[c as usize] > 0) {
                r = format!("{}{}{}", &t[..i], c as char, (97..=122).flat_map(|x| vec![x as char; f[x as usize] - (x == c) as usize]).join(""));
            }
            if f[b as usize] == 0 { break }; f[b as usize] -= 1;
        } r
    }