LeetCode Entry

1625. Lexicographically Smallest String After Applying Operations

19.10.2025 medium 2025 kotlin rust

Min string after shifting by b and rotating odd indice by a

1625. Lexicographically Smallest String After Applying Operations medium blog post substack youtube

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1147

Problem TLDR

Min string after shifting by b and rotating odd indice by a #medium #bruteforce

Intuition

    // s is small, up to 100
    // if b is even:    12345678  34567812  56781234  78123456
    //                  1234567   3456712   5671234   7123456 2345671 4567123  6712345  1234567
    // if b is odd:     12345678  45678123  78123456  23456781  56781234 81234567 3.. 6..
    //                  1234567   4567123   7123456   3456712  6712345  2345671 5671234
    // so only when b%2 == 0 && size%2 == 0 we don't have access to all elements
    // the size is small, we can brute-force every possible rotation to get the minimum
    // rotation of digit: 1, a = 3: 1,4,7,0,3,6,9,2
    // 25 minute: forgot about odd indices
    // 40 minute: we can't change indices independently ?
    // 43987654 b=3
    // *  *  *
    // 01234567
    // 34567012
    // 67012345
    // 12345670
    // 45670123
    // 70123456
    // 23456701
    // 56701234
    // 01234567  so, all indices can be on the first position
    // 50 minute: wrong steps calculation
    // 12345678901234 14, step=6
    // 58016941393090
    // 41393090580169

    //     * *     *
    // 123456789abcde
    // 56789abcde1234

Two situations:

1. odd length and odd shift: we can rotate only odd indices
2. otherwise we can rotate odd indices and even indices

Approach

• rotations should be for all indices; separate value of rotations for odd and even

Complexity

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

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

Code

// 50ms
    fun findLexSmallestString(s: String, a: Int, b: Int) = s.indices.minOf { i ->
        fun rot(c: Char) = (0..9).minBy { (c-'0'+it*a)%10 }
        var sh = s.drop((i*b)%s.length)+s.take((i*b)%s.length)
        val eo = listOf(if (s.length % 2 == 0 && b % 2 == 0) 0 else rot(sh[0]), rot(sh[1]))
        sh.mapIndexed { i,c -> '0'+(c-'0' + eo[i%2]*a)%10 }.joinToString("")
    }

// 0ms
    pub fn find_lex_smallest_string(s: String, a: i32, b: i32) -> String {
        (0..s.len()).map(|i| {
            let rot = |c: u8| {(0..10).min_by_key(|&x| (c - b'0' +  x * a as u8) % 10).unwrap()};
            let sh = s.chars().cycle().skip((i * b as usize)%s.len()).take(s.len()).collect::<String>();
            let eo = [if (s.len() as i32|b)&1 < 1 {0} else {rot(sh.as_bytes()[0])}, rot(sh.as_bytes()[1])];
            sh.bytes().enumerate().map(|(i, c)| (b'0' + (c - b'0' + eo[i&1]*a as u8)%10) as char).collect()
        }).min().unwrap()
    }