LeetCode Entry

3304. Find the K-th Character in String Game I

3.07.2025 easy 2025 kotlin rust

kth char after appending rotated self

3304. Find the K-th Character in String Game I easy blog post substack youtube 1.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1038

Problem TLDR

kth char after appending rotated self #easy

Intuition

Simulation is accepted.

Some patterns:

    // 01 23 4567 8910     16               32
    // 01 12 1223 13
    // ab bc bccd bccd.... bccd............ bccd........
    //                 cdde
    //                 12
  • the b is always at pos power of two
  • each time we double into the left part and right part
  • left is untouched, right is shifted once against previous
  • left is at POS%2 == 0, right is at POS%2 > 0

Approach

  • do shift at each set bit
  • ‘a’ will never overflow ‘z’, the first ‘z’ is at (1 << 25) - 1 position

Complexity

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

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

Code


// 13ms
    fun kthCharacter(k: Int): Char {
        var s = listOf('a')
        while (s.lastIndex < k - 1) s += s.map { it + 1 }
        return s[k - 1]
    }



// 1ms
    fun kthCharacter(k: Int): Char {
        var k = k - 1; var c = 'a'
        while (k > 0) { c += k % 2; k /= 2 }
        return c
    }



// 0ms
    fun kthCharacter(k: Int): Char {
        fun x(k: Int): Char = if (k == 0) 'a' else x(k / 2) + k % 2
        return x(k - 1)
    }



// 0ms
    fun kthCharacter(k: Int, l: Int = 1): Char =
        if (k == l) 'a' else kthCharacter((k - l) / 2, 0) + (k - l) % 2



// 0ms
    fun kthCharacter(k: Int) = 'a' + (k - 1).countOneBits()



// 0ms
    pub fn kth_character(k: i32) -> char {
        "abcdefghi".as_bytes()[(k - 1).count_ones() as usize] as char
    }



// 0ms
    char kthCharacter(int k) {
        return 'a' + __builtin_popcount(k - 1);
    }