3307. Find the K‑th Character in String Game II
Introduction
In this article we solve the LeetCode‑style problem titled “3307. Find the K‑th Character in String Game II.”
The task is to determine which character is removed at the k‑th operation of a simple game played on a given string. The description is concise, but the underlying process can be misunderstood, so a clear definition of the rules is essential before any algorithmic thinking begins. The main keyword k‑th character appears throughout the statement, and the solution must handle strings of length up to 10⁵ efficiently.
Problem Understanding
You are given a string s consisting of lowercase English letters and an integer k (1 ≤ k ≤ |s|).
The game proceeds as follows:
- Remove the k‑th character of the current string, counting from the left (1‑indexed).
- After the removal, the remaining parts of the string are concatenated, forming a new string.
- Repeat steps 1–2 until the string length becomes smaller than k; at that point the game stops.
The required answer is the character that is removed exactly at the k‑th operation (i.e., the character removed during the k‑th iteration).
Important note: The game can only continue while the current string length is at least k. That's why, to be able to perform the k‑th removal we must have enough characters left after each removal. This leads to a simple feasibility condition that we will examine next Surprisingly effective..
Key Observations
- Deterministic removal order – Because the rule always selects the same positional index (the k‑th character) from the current string, the sequence of removed characters follows a predictable pattern.
- Index shift – After each removal, all characters that were positioned to the right of the removed element shift left by one position. This means the original index of the character removed at step i is (k‑1) + (i‑1).
- Feasibility condition – To reach the k‑th removal we need the original string length n to satisfy n ≥ 2k − 1. If this condition is not met, the game stops before the k‑th operation and the problem’s constraints guarantee that such inputs are not provided.
These observations let us compute the answer in constant time without simulating every removal Small thing, real impact..
Algorithm
-
Let n = s.length.
-
Verify the feasibility condition n ≥ 2k − 1 (the problem guarantees this, but a check can be added for safety).
-
Compute the original index of the character removed at the k‑th operation:
[ \text{idx} = (k-1) + (k-1) = 2k - 2 ]
-
Return the character s[idx] (0‑based indexing).
If you prefer a simulation approach (useful for verification or when the feasibility condition is uncertain), you can use a list or deque and repeatedly pop the element at position k‑1 (adjusted for the shrinking size). The simulation runs in O(k) time, which is acceptable for the given constraints.
Pseudocode
function kthCharacter(s, k):
n = length(s)
if n < 2*k - 1:
return '' // should not happen per constraints
idx = 2*k - 2 // zero‑based index in the original string
return s[idx]
Example Walkthrough
Example 1
- s = "abcde", k = 2
n = 5, 2k‑1 = 3 → condition satisfied.
idx = 2·2 − 2 = 2 → s[2] = 'c'.
The removal sequence is:
1️⃣ remove 2nd char → 'b' (index 1) → string becomes "acde"
2️⃣ remove 2nd char → 'c' (original index 2) → answer 'c'.
Example 2
- s = "xyz", k = 1
n = 3, 2k‑1 = 1 → condition satisfied.
idx = 2·1 − 2 = 0 → s[0] = 'x'.
The first removal is the 1st character, so the answer is 'x'.
Example 3
- s = "programming", k = 4
n = 11, 2k‑1 = 7 → condition satisfied.
idx = 2·4 − 2 = 6 → s[6] = 'a'.
Thus the character removed at the 4‑th operation is 'a'.
These examples illustrate that the answer can be obtained directly from the original string without any looping.
Implementation Tips
- Language‑specific indexing – Remember that most programming languages use 0‑based indexing for arrays, so the formula 2k − 2 must be adjusted accordingly.
- Edge cases – If the input violates the feasibility condition (which the official test data avoid), return an empty string or handle the situation gracefully.
- Data structures – A simple array access is sufficient; no extra containers are needed, giving the solution O(1) time and O(1) extra space.
- Testing – Verify the solution against the examples above and against random strings to ensure the index calculation never exceeds the string bounds.
Complexity Analysis
- Time complexity: O(1) – the algorithm performs a constant amount of arithmetic and a single array lookup.
- Space complexity: O(1) – only a few integer variables are used, regardless of the input size.
Conclusion
The “k‑th character in string game II” problem reduces to a straightforward index computation once the deterministic nature of the removal process is understood. By recognizing that the character removed at the k‑th operation resides at original position 2k − 2, we can answer the query instantly with constant time and space. This approach not only satisfies the performance requirements of large inputs but also provides a clear, easy‑to‑explain solution that aligns with the problem’s constraints.
