This content originally appeared on DEV Community and was authored by Md. Rishat Talukder
🔹 Problem: 3307 Find the K-th Character in String Game II
Difficulty: #Hard
Tags: #BitManipulation, #BinaryTree, #Simulation, #Math
📝 Problem Summary
You're given a list of binary operations and an integer k. The operations describe a string-building process where:
-
0→ Duplicate the current string. -
1→ Duplicate and rotate all characters (i.e.,'a'→'b','z'→'a').
Starting from the character 'a', the string grows exponentially. You must return the character at the k-th position (1-indexed) in the final string. Since the string size can grow beyond 2^60, directly building the string is impossible.
🧠 My Thought Process
Brute Force Idea:
My first dumb-dumb instinct was to actually simulate the whole string. After thinking for two seconds and glancing atk <= 10^14, I immediately panicked. 🫠
Clearly, building the string is impossible. So I guessed maybe I should reverse simulate or use some kind of tree trick.-
Optimized Strategy:
I saw someone mention using bit manipulation and tree traversal. That made me realize the string growth follows a binary tree-like structure where each operation is a node:- Each operation level doubles the string length.
- If the op is
1, you also rotate characters.
So instead of building the string forward, you trace backwards from k to find how many +1 (rotations) were applied to 'a'. This only requires O(log k) steps.
The idea is to walk back the path to the first 'a', tracking how many times a rotation occurred on the path to position k.
-
Algorithm Used:
Bit Manipulation+Reverse Simulation
⚙️ Code Implementation (Python)
class Solution:
def kthCharacter(self, k: int, operations: List[int]) -> str:
ans = 0
while k != 1:
t = k.bit_length() - 1
if (1 << t) == k:
t -= 1
k -= 1 << t
if operations[t]:
ans += 1
return chr(ord("a") + (ans % 26))
⏱️ Time & Space Complexity
-
Time:
O(log k)→ each step reducesksignificantly -
Space:
O(1)→ only a few variables
🧩 Key Takeaways
- ✅ Learned how exponential string-building problems can be reversed via bit tricks.
- 💡 The use of
bit_length()to identify subtree levels is brilliant and elegant. - 💭 These problems scare me because of the size of the numbers involved, but breaking them down reveals a simple, elegant path.
🔁 Reflection (Self-Check)
[ ] Could I solve this without help?
❌ I had the general reverse idea but couldn’t optimize it down. I panicked and opened discussion 😅[ ] Did I write code from scratch?
❌ No, I followed a solution after understanding it deeply.[x] Did I understand why it works?
✅ Yes, and honestly I feel proud now that I can explain it.[x] Will I be able to recall this in a week?
✅ I think so, now that I understand the binary tree traversal pattern.
📚 Related Problems
- [[848. Shifting Letters]]
🚀 Progress Tracker
| Metric | Value |
|---|---|
| Day | 36 |
| Total Problems Solved | 371 |
| Confidence Today | 😐 |
This content originally appeared on DEV Community and was authored by Md. Rishat Talukder
Md. Rishat Talukder | Sciencx (2025-07-04T05:39:47+00:00) 🧠 Solving LeetCode Until I Become Top 1% — Day `37`. Retrieved from https://www.scien.cx/2025/07/04/%f0%9f%a7%a0-solving-leetcode-until-i-become-top-1-day-37/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.