Loading…

mediumBit ManipulationSometimes asked

Cipher

Q: How do you solve Cipher using the Brute Force — Recompute Each Bit's Window approach?

When to use it: Say this first: it inverts the encoder definition literally before you find the telescoping shortcut. Invert the encoder directly, one bit at a time. **The inversion.** By definition `enc[i] = s[i] ^ s[i-1] ^ … ^ s[i-k+1]`. Everything in that XOR except `s[i]` has already been decoded by the time we reach position `i`. So `s[i] = enc[i] ^ (s[i-1] ^ … ^ s[i-k+1])`, treating indices below 0 as absent. Seed with `s[0] = enc[0]` since the first window holds only `s[0]`. **How the loop runs.** For each `i`, gather the XOR of the previously decoded bits in the window `[max(0, i-k+1), i-1]`, then XOR with `enc[i]` to recover `s[i]`. **Why it's correct but slow.** It exactly reverses the encoding, so it always produces the right `s`. But recomputing the window XOR from scratch at every position does up to `k-1` XORs per bit, giving `O(n·k)`. With both `n` and `k` up to `10⁶`, that's `~10¹²` operations — hopeless. The fix is to avoid recomputing the overlap, which is what the telescoping recurrence does. Time complexity: O(n·k). Space complexity: O(n).

Q: How do you solve Cipher using the Telescoping Recurrence — Adjacent-Window Difference (Optimal) approach?

When to use it: The answer they want. Say 'XOR two adjacent encoded bits to cancel the overlap: s[i] = enc[i] ^ enc[i-1] ^ (s[i-k] if i≥k)'. Cancel the window overlap instead of recomputing it. **The telescoping identity.** The window for position `i` is `s[i] ^ s[i-1] ^ … ^ s[i-k+1]`; for position `i-1` it is `s[i-1] ^ s[i-2] ^ … ^ s[i-k]`. These two windows overlap in the k−1 positions `i-1 … i-k+1`. XORing the two encoded bits cancels that shared block: `enc[i] ^ enc[i-1] = s[i] ^ s[i-k]` because `s[i]` is in the first window but not the second (it just entered), and `s[i-k]` is in the second but not the first (it just left). Everything in between appears in both and cancels. **Solve for s[i].** Rearranging, `s[i] = enc[i] ^ enc[i-1] ^ s[i-k]`. The leaving bit `s[i-k]` only exists once `i ≥ k`; before that nothing has dropped out of the window, so the term is omitted. The seed is `s[0] = enc[0]` (first window = just s[0]). **Why it must be enc[i-1], not s[i-1].** The cancellation is an algebraic identity between the two ENCODED values. Substituting `s[i-1]` for `enc[i-1]` breaks it and produces wrong bits from the third position onward — a tempting but incorrect shortcut. **Why it's fast.** Each bit costs two XORs and one array read: O(1). One left-to-right pass decodes the whole string in O(n), which is essential at n, k up to 10⁶. Time complexity: O(n). Space complexity: O(n).

Bit Manipulation · 16 of 20 · 9 min

A binary string s of length n is encoded as follows: make k copies of s, shift the j-th copy right by j positions (j = 0..k−1), align them, and XOR each column. The result is an encoded binary string of length n + k − 1. Given the encoded string and the integers n and k, recover and return the original string s.

In plain English

Stacking k right-shifted copies of s and XORing columns means column i collects s at positions i, i−1, …, i−k+1 (whichever are in range). So enc[i] is the XOR of the last up-to-k bits of s ending at i — a fixed-width sliding XOR window. Decoding means inverting that window. Because XOR cancels repeats, comparing two neighbouring columns wipes out everything they share and exposes exactly the one bit that entered and the one that left.

Examples

Example 1

Input: encoded = "11101", n = 4, k = 2
Output: 1011
Note: s[0]=enc[0]=1; s[1]=enc[1]^enc[0]=1^1=0; s[2]=enc[2]^enc[1]^s[0]=1^1^1=1; s[3]=enc[3]^enc[2]^s[1]=0^1^0=1 → "1011". Check: encoding "1011" with k=2 gives "11101".

Example 2

Input: encoded = "1110100110", n = 7, k = 4
Output: 1001010
Note: The classic example: four shifted copies of "1001010" XORed column-wise produce "1110100110"; the recurrence reconstructs "1001010".

Example 3

Input: encoded = "101", n = 3, k = 1
Output: 101
Note: With k = 1 the window is a single bit, so enc == s. Decoding returns the input unchanged.

Constraints

1 ≤ n ≤ 10⁶ (length of the original string s)
1 ≤ k ≤ 10⁶
Length of the encoded string is exactly n + k − 1
s and the encoded string contain only the characters '0' and '1'

Clarifying questions4First question: What exactly is the relationship between enc[i] and s?Explore questions

Q1.What exactly is the relationship between enc[i] and s?
enc[i] = s[i] XOR s[i−1] XOR … XOR s[i−k+1], where any index < 0 or ≥ n contributes 0. The encoded string has length n + k − 1.
Q2.How do I get s[0]?
The first column contains only s[0] (no earlier bits exist), so s[0] = enc[0].
Q3.Why use enc[i] XOR enc[i−1] rather than s[i−1]?
Two adjacent windows overlap in k−1 positions; XORing the two encoded bits cancels that shared overlap, leaving s[i] XOR s[i−k]. That cancellation only happens between the ENCODED values, so it must be enc[i−1], not s[i−1].
Q4.What about the boundary when i < k?
Before index k, the window hasn't dropped any bit yet, so there is no s[i−k] term — only enc[i] XOR enc[i−1] (plus s[0] = enc[0] as the seed).

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Decode a binary string. The encoder takes the original s of length n, writes k right-shifted copies, and XORs the columns, giving an encoded string of length n+k−1 where enc[i] = XOR of s[i−k+1 .. i] (clamped to valid indices). To invert: s[0] = enc[0]; for i ≥ 1, s[i] = enc[i] XOR enc[i−1] XOR (s[i−k] if i ≥ k else 0). The enc[i] XOR enc[i−1] term cancels everything shared between two adjacent windows, leaving just the entering bit s[i] and the leaving bit s[i−k]. Reconstructing each bit naively by re-XORing its window is O(n·k); the difference recurrence is O(n).

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can model the encoder as a sliding XOR window and invert it by telescoping adjacent encoded bits, reaching an O(n) recurrence instead of recomputing each bit's window in O(k).

Where candidates slip

Recomputing each bit's window XOR (O(n·k) and too slow), using s[i-1] instead of enc[i-1] in the recurrence, or mis-handling the i < k boundary where no bit has left the window yet.

How to stand out

Write enc[i] = XOR of the last k bits of s, observe enc[i] ^ enc[i-1] = s[i] ^ s[i-k], and derive s[i] = enc[i] ^ enc[i-1] ^ (s[i-k] if i≥k) — a single linear pass with O(1) per bit.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Recompute Each Bit's Window	`O(n·k)`	`O(n)`	Say this first: it inverts the encoder definition literally before you find the telescoping shortcut.	Read
2	Telescoping Recurrence — Adjacent-Window Difference (Optimal)Optimal	`O(n)`	`O(n)`	The answer they want. Say 'XOR two adjacent encoded bits to cancel the overlap: s[i] = enc[i] ^ enc[i-1] ^ (s[i-k] if i≥k)'.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewRecover s from encodedRecompute each window?YesTelescopeExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Recompute Each Bit's Window

TimeO(n·k)SpaceO(n)

Say this first: it inverts the encoder definition literally before you find the telescoping shortcut.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

From enc[i] = s[i] XOR (the previous up-to-k−1 already-decoded bits), solve for s[i].

2Hint 2Explore hint

s[0] = enc[0]. For i ≥ 1, s[i] = enc[i] XOR (s[i−1] XOR … XOR s[i−k+1]), clamping the lower index at 0.

3Hint 3Explore hint

Recomputing that inner XOR for every i costs up to k work each → O(n·k). Correct, but too slow when n and k are both 10⁶.

A · Core idea

Invert the encoder directly, one bit at a time.

The inversion. By definition enc[i] = s[i] ^ s[i-1] ^ … ^ s[i-k+1]. Everything in that XOR except s[i] has already been decoded by the time we reach position i. So s[i] = enc[i] ^ (s[i-1] ^ … ^ s[i-k+1]), treating indices below 0 as absent. Seed with s[0] = enc[0] since the first window holds only s[0].

How the loop runs. For each i, gather the XOR of the previously decoded bits in the window [max(0, i-k+1), i-1], then XOR with enc[i] to recover s[i].

Why it's correct but slow. It exactly reverses the encoding, so it always produces the right s. But recomputing the window XOR from scratch at every position does up to k-1 XORs per bit, giving O(n·k). With both n and k up to 10⁶, that's ~10¹² operations — hopeless. The fix is to avoid recomputing the overlap, which is what the telescoping recurrence does.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

encoded = "11101", n = 4, k = 2

Interactive diagram

Recomputing each window

i=0

Active call / nodeSupporting contextReturned stateNot active

Every bit re-XORs up to k−1 prior bits — the overlap the optimal solution skips.

Final result1011

C · Code with teaching comments

Reference implementation previewpublic String cipher(int n, int k, String encoded) { int[] s = new int[n]; s[0] = encoded.charAt(0) - '0'; for (int i = 1; i < n; i++) { int window = 0;Explore the full code

solution.javaJava

Brute Force — Recompute Each Bit's Window — reference

3 teaching notes

1
public String cipher(int n, int k, String encoded) {
2
    int[] s = new int[n];
3
    // The first column contains only s[0], so it equals enc[0].
4
    s[0] = encoded.charAt(0) - '0';
5
    for (int i = 1; i < n; i++) {
6
        int window = 0;
7
        // Walk the already-decoded bits in this position's window; clamp the lower
8
        // bound at 0.
9
        for (int j = Math.max(0, i - k + 1); j <= i - 1; j++) {
10
            window ^= s[j];                  // XOR of previously decoded bits
11
        }
12
        // Remove the known window bits from enc[i] to expose s[i].
13
        s[i] = (encoded.charAt(i) - '0') ^ window;
14
    }
15
    StringBuilder sb = new StringBuilder();
16
    for (int b : s) sb.append(b);
17
    return sb.toString();
18
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.18 lines

D · Why it works and complexityO(n·k) timeO(n) spaceOpen the invariant and proofExplore the proof

Two consecutive windows share k−1 bits. Recomputing that shared region every step is the wasted work; the optimal approach cancels it with a single XOR of adjacent encoded bits.

ComplexityO(n·k) time, O(n) space — Each of the n bits recomputes a window of up to k−1 previously-decoded bits → O(n·k) in the worst case (~10¹² when both are 10⁶), which is far too slow.

E · Edge cases and pitfalls3Forgetting to clamp the window's lower index at 0 for the first k−1 positions.Explore edge cases

Pitfalls

Forgetting to clamp the window's lower index at 0 for the first k−1 positions.
Recomputing the full window each step — the O(n·k) blowup that times out at 10⁶.
Off-by-one on the window: it covers s[i−k+1 .. i−1] of already-decoded bits, not including i.

03.2

Approach 2 of 2 · Optimal

Telescoping Recurrence — Adjacent-Window Difference (Optimal)

TimeO(n)SpaceO(n)

The answer they want. Say 'XOR two adjacent encoded bits to cancel the overlap: s[i] = enc[i] ^ enc[i-1] ^ (s[i-k] if i≥k)'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Write out enc[i] and enc[i−1] as XORs of overlapping windows. What survives when you XOR them together?

2Hint 2Explore hint

The two windows share s[i−1 .. i−k+1]; those cancel, leaving enc[i] ^ enc[i−1] = s[i] ^ s[i−k].

3Hint 3Explore hint

So s[i] = enc[i] ^ enc[i−1] ^ s[i−k], with the s[i−k] term only when i ≥ k. Seed s[0] = enc[0]. One pass, O(1) per bit.

A · Core idea

Cancel the window overlap instead of recomputing it.

The telescoping identity. The window for position i is s[i] ^ s[i-1] ^ … ^ s[i-k+1]; for position i-1 it is s[i-1] ^ s[i-2] ^ … ^ s[i-k]. These two windows overlap in the k−1 positions i-1 … i-k+1. XORing the two encoded bits cancels that shared block:

enc[i] ^ enc[i-1] = s[i] ^ s[i-k]

because s[i] is in the first window but not the second (it just entered), and s[i-k] is in the second but not the first (it just left). Everything in between appears in both and cancels.

Solve for s[i]. Rearranging, s[i] = enc[i] ^ enc[i-1] ^ s[i-k]. The leaving bit s[i-k] only exists once i ≥ k; before that nothing has dropped out of the window, so the term is omitted. The seed is s[0] = enc[0] (first window = just s[0]).

Why it must be enc[i-1], not s[i-1]. The cancellation is an algebraic identity between the two ENCODED values. Substituting s[i-1] for enc[i-1] breaks it and produces wrong bits from the third position onward — a tempting but incorrect shortcut.

Why it's fast. Each bit costs two XORs and one array read: O(1). One left-to-right pass decodes the whole string in O(n), which is essential at n, k up to 10⁶.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

encoded = "11101", n = 4, k = 2

Interactive diagram

Adjacent windows cancel their overlap

i=0

Active call / nodeSupporting contextReturned stateNot active

enc[i] ^ enc[i-1] wipes the shared k−1 bits, exposing s[i] and s[i-k].

Final result1011

C · Code with teaching comments

solution.javaJava

Telescoping Recurrence — Adjacent-Window Difference (Optimal) — optimal

4 teaching notes

1
public String cipher(int n, int k, String encoded) {
2
    char[] s = new char[n];
3
    int prev = encoded.charAt(0) - '0';
4
    s[0] = (char) ('0' + prev);              // first window is just s[0]
5
    for (int i = 1; i < n; i++) {
6
        int cur = encoded.charAt(i) - '0';
7
        int bit = cur ^ (encoded.charAt(i - 1) - '0');   // enc[i] ^ enc[i-1] = s[i] ^ s[i-k]
8
        // Only once i ≥ k has a bit (s[i-k]) actually left the window.
9
        if (i >= k) {
10
            bit ^= (s[i - k] - '0');         // remove the bit that left the window
11
        }
12
        s[i] = (char) ('0' + bit);
13
    }
14
    return new String(s);
15
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.15 lines

D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proof

Decoding a sliding XOR window telescopes: neighbouring encoded bits cancel their shared overlap, exposing only the bit that entered (s[i]) and the bit that left (s[i−k]). That single observation turns an O(n·k) re-summation into an O(n) recurrence.

ComplexityO(n) time, O(n) space — A single left-to-right pass computing each s[i] from two encoded bits and one earlier decoded bit — O(1) per position, O(n) total, with O(n) space for the output.

E · Edge cases and pitfalls6k = 1 — Window width 1 → enc == s. The recurrence gives s[i] = enc[i] ^ enc[i-1] ^ s[i-1] = enc[i], returning the input unchanged.Explore edge cases

Edge cases handled

k = 1Window width 1 → enc == s. The recurrence gives s[i] = enc[i] ^ enc[i-1] ^ s[i-1] = enc[i], returning the input unchanged.
n = 1Only s[0] = enc[0]; the loop never runs.
encoded = "1110100110", n = 7, k = 4Reconstructs "1001010", the canonical worked example.

Pitfalls

Using s[i-1] instead of enc[i-1] — breaks the cancellation identity from i = 2 onward.
Applying the s[i-k] term when i < k (no bit has left yet) and corrupting the early bits.
Reading enc[i-1] off the partially built s array rather than the original encoded string.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic String cipher(int n, int k, String encoded) { char[] s = new char[n]; int prev = encoded.charAt(0) - '0'; s[0] = (char) ('0' + prev); // first window is just s[0] for (int i = 1; i < n; i++) {Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Using s[i-1] instead of enc[i-1]

The telescoping identity enc[i] ^ enc[i-1] = s[i] ^ s[i-k] holds for the ENCODED values. Swapping in the decoded s[i-1] breaks the cancellation and yields wrong bits from position 2 on.

Explore the code comparison

Don't write this

bit = int(encoded[i]) ^ s[i - 1]      # wrong: should be enc[i-1]
if i >= k: bit ^= s[i - k]

Write this instead

bit = int(encoded[i]) ^ int(encoded[i - 1])
if i >= k: bit ^= s[i - k]

Applying the leaving term too early

Before index k, the window hasn't dropped any bit, so there is no s[i-k] to remove. Adding it (or indexing s[i-k] with a negative index) corrupts the first bits.

Explore the code comparison

Don't write this

int bit = cur ^ (encoded.charAt(i - 1) - '0');
bit ^= (s[i - k] - '0');             // i-k can be negative when i < k

Write this instead

int bit = cur ^ (encoded.charAt(i - 1) - '0');
if (i >= k) bit ^= (s[i - k] - '0');

O(n·k) window recomputation

Re-XORing up to k−1 prior bits for every position is correct but quadratic-ish; at n, k = 10⁶ it's ~10¹² ops and times out. Telescope instead.

Explore the code comparison

Don't write this

for i in range(1, n):
    window = 0
    for j in range(max(0, i - k + 1), i):   # O(k) each
        window ^= s[j]
    s[i] = int(encoded[i]) ^ window

Write this instead

for i in range(1, n):
    bit = int(encoded[i]) ^ int(encoded[i - 1])
    if i >= k: bit ^= s[i - k]
    s[i] = bit

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Invert a sliding XOR window via adjacent-window difference

Code pattern to memorize

s[0] = enc[0]
for i in 1..n-1:
    s[i] = enc[i] ^ enc[i-1]
    if i >= k: s[i] ^= s[i-k]
# because enc[i] ^ enc[i-1] = s[i] ^ s[i-k]  (window shifted by one)

Rules to remember

1Encoding is a sliding XOR window of width k: enc[i] = s[i] ^ s[i-1] ^ … ^ s[i-k+1], with out-of-range s treated as 0. Encoded length is n + k − 1.
2Adjacent encoded bits differ by exactly the bit entering and the bit leaving the window: enc[i] ^ enc[i-1] = s[i] ^ s[i-k].
3Rearranged, s[i] = enc[i] ^ enc[i-1] ^ s[i-k], and the s[i-k] term only applies once i ≥ k (otherwise nothing has left the window yet).
4Seed with s[0] = enc[0] because the first window contains only s[0].
5Use enc[i-1], NOT s[i-1], in the recurrence — the cancellation identity is between consecutive ENCODED bits. Substituting s[i-1] is a common but wrong shortcut.

Use this pattern when

Decode/invert a stream produced by XOR over a sliding window
Telescoping: adjacent prefix/window values cancel to a tiny difference
Reconstruct a sequence from cumulative or windowed XOR sums
Any 'each output mixes the last k inputs by XOR' inversion

Choose another pattern when

The mixing op doesn't cancel on repeats (sum/product window) → need prefix arithmetic, not XOR cancellation
Window width isn't fixed / varies per position → the clean difference identity breaks
You need the encoder, not the decoder → just compute the windowed XOR forward
Encoded length doesn't equal n + k − 1 → re-derive the model before coding

Interview takeaway

Encoding is a width-k sliding XOR window; decoding telescopes it. Two adjacent encoded bits cancel everything except the entering bit s[i] and the leaving bit s[i−k], giving s[i] = enc[i] ^ enc[i−1] ^ (s[i−k] if i≥k) — one O(n) pass instead of re-summing each window.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternInvert a sliding XOR window by telescoping. When each output XORs a fixed window of inputs, neighbouring outputs cancel their overlap, exposing only the entering and leaving terms: s[i] = enc[i] ^ enc[i-1] ^ s[i-k]. This converts an O(n·k) reconstruction into an O(n) recurrence — the XOR analogue of prefix-sum differencing.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Flipping Bits
Another XOR-as-toggle problem — here a full-width complement via an all-ones mask.
Sansa and XOR
Also reasons about which contributions survive XOR over overlapping windows.
XOR Queries of a Subarray
Coming soon
Prefix-XOR telescoping: range XOR = prefix[r] ^ prefix[l-1], the same cancellation idea.

Same pattern

←

Sum vs XOR

Continue · Next problem

Counter Game

mediumBit ManipulationSometimes asked

Cipher

Bit Manipulation · 16 of 20 · 9 min

In plain English

Examples

Example 1

Input: encoded = "11101", n = 4, k = 2
Output: 1011
Note: s[0]=enc[0]=1; s[1]=enc[1]^enc[0]=1^1=0; s[2]=enc[2]^enc[1]^s[0]=1^1^1=1; s[3]=enc[3]^enc[2]^s[1]=0^1^0=1 → "1011". Check: encoding "1011" with k=2 gives "11101".

Example 2

Input: encoded = "1110100110", n = 7, k = 4
Output: 1001010
Note: The classic example: four shifted copies of "1001010" XORed column-wise produce "1110100110"; the recurrence reconstructs "1001010".

Example 3

Input: encoded = "101", n = 3, k = 1
Output: 101
Note: With k = 1 the window is a single bit, so enc == s. Decoding returns the input unchanged.

Constraints

1 ≤ n ≤ 10⁶ (length of the original string s)
1 ≤ k ≤ 10⁶
Length of the encoded string is exactly n + k − 1
s and the encoded string contain only the characters '0' and '1'

Clarifying questions4First question: What exactly is the relationship between enc[i] and s?Explore questions

Q1.What exactly is the relationship between enc[i] and s?
enc[i] = s[i] XOR s[i−1] XOR … XOR s[i−k+1], where any index < 0 or ≥ n contributes 0. The encoded string has length n + k − 1.
Q2.How do I get s[0]?
The first column contains only s[0] (no earlier bits exist), so s[0] = enc[0].
Q3.Why use enc[i] XOR enc[i−1] rather than s[i−1]?
Two adjacent windows overlap in k−1 positions; XORing the two encoded bits cancels that shared overlap, leaving s[i] XOR s[i−k]. That cancellation only happens between the ENCODED values, so it must be enc[i−1], not s[i−1].
Q4.What about the boundary when i < k?
Before index k, the window hasn't dropped any bit yet, so there is no s[i−k] term — only enc[i] XOR enc[i−1] (plus s[0] = enc[0] as the seed).

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can model the encoder as a sliding XOR window and invert it by telescoping adjacent encoded bits, reaching an O(n) recurrence instead of recomputing each bit's window in O(k).

Where candidates slip

Recomputing each bit's window XOR (O(n·k) and too slow), using s[i-1] instead of enc[i-1] in the recurrence, or mis-handling the i < k boundary where no bit has left the window yet.

How to stand out

Write enc[i] = XOR of the last k bits of s, observe enc[i] ^ enc[i-1] = s[i] ^ s[i-k], and derive s[i] = enc[i] ^ enc[i-1] ^ (s[i-k] if i≥k) — a single linear pass with O(1) per bit.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Recompute Each Bit's Window	`O(n·k)`	`O(n)`	Say this first: it inverts the encoder definition literally before you find the telescoping shortcut.	Read
2	Telescoping Recurrence — Adjacent-Window Difference (Optimal)Optimal	`O(n)`	`O(n)`	The answer they want. Say 'XOR two adjacent encoded bits to cancel the overlap: s[i] = enc[i] ^ enc[i-1] ^ (s[i-k] if i≥k)'.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Recompute Each Bit's Window

TimeO(n·k)SpaceO(n)

Say this first: it inverts the encoder definition literally before you find the telescoping shortcut.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

From enc[i] = s[i] XOR (the previous up-to-k−1 already-decoded bits), solve for s[i].

2Hint 2Explore hint

s[0] = enc[0]. For i ≥ 1, s[i] = enc[i] XOR (s[i−1] XOR … XOR s[i−k+1]), clamping the lower index at 0.

3Hint 3Explore hint

Recomputing that inner XOR for every i costs up to k work each → O(n·k). Correct, but too slow when n and k are both 10⁶.

A · Core idea

Invert the encoder directly, one bit at a time.

How the loop runs. For each i, gather the XOR of the previously decoded bits in the window [max(0, i-k+1), i-1], then XOR with enc[i] to recover s[i].

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

encoded = "11101", n = 4, k = 2

Interactive diagram

Recomputing each window

i=0

Active call / nodeSupporting contextReturned stateNot active

Every bit re-XORs up to k−1 prior bits — the overlap the optimal solution skips.

Final result1011

C · Code with teaching comments

solution.javaJava

Brute Force — Recompute Each Bit's Window — reference

3 teaching notes

1
public String cipher(int n, int k, String encoded) {
2
    int[] s = new int[n];
3
    // The first column contains only s[0], so it equals enc[0].
4
    s[0] = encoded.charAt(0) - '0';
5
    for (int i = 1; i < n; i++) {
6
        int window = 0;
7
        // Walk the already-decoded bits in this position's window; clamp the lower
8
        // bound at 0.
9
        for (int j = Math.max(0, i - k + 1); j <= i - 1; j++) {
10
            window ^= s[j];                  // XOR of previously decoded bits
11
        }
12
        // Remove the known window bits from enc[i] to expose s[i].
13
        s[i] = (encoded.charAt(i) - '0') ^ window;
14
    }
15
    StringBuilder sb = new StringBuilder();
16
    for (int b : s) sb.append(b);
17
    return sb.toString();
18
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.18 lines

D · Why it works and complexityO(n·k) timeO(n) spaceOpen the invariant and proofExplore the proof

Two consecutive windows share k−1 bits. Recomputing that shared region every step is the wasted work; the optimal approach cancels it with a single XOR of adjacent encoded bits.

E · Edge cases and pitfalls3Forgetting to clamp the window's lower index at 0 for the first k−1 positions.Explore edge cases

Pitfalls

Forgetting to clamp the window's lower index at 0 for the first k−1 positions.
Recomputing the full window each step — the O(n·k) blowup that times out at 10⁶.
Off-by-one on the window: it covers s[i−k+1 .. i−1] of already-decoded bits, not including i.

03.2

Approach 2 of 2 · Optimal

Telescoping Recurrence — Adjacent-Window Difference (Optimal)

TimeO(n)SpaceO(n)

The answer they want. Say 'XOR two adjacent encoded bits to cancel the overlap: s[i] = enc[i] ^ enc[i-1] ^ (s[i-k] if i≥k)'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Write out enc[i] and enc[i−1] as XORs of overlapping windows. What survives when you XOR them together?

2Hint 2Explore hint

The two windows share s[i−1 .. i−k+1]; those cancel, leaving enc[i] ^ enc[i−1] = s[i] ^ s[i−k].

3Hint 3Explore hint

So s[i] = enc[i] ^ enc[i−1] ^ s[i−k], with the s[i−k] term only when i ≥ k. Seed s[0] = enc[0]. One pass, O(1) per bit.

A · Core idea

Cancel the window overlap instead of recomputing it.

enc[i] ^ enc[i-1] = s[i] ^ s[i-k]

because s[i] is in the first window but not the second (it just entered), and s[i-k] is in the second but not the first (it just left). Everything in between appears in both and cancels.

Why it's fast. Each bit costs two XORs and one array read: O(1). One left-to-right pass decodes the whole string in O(n), which is essential at n, k up to 10⁶.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

encoded = "11101", n = 4, k = 2

Interactive diagram

Adjacent windows cancel their overlap

i=0

Active call / nodeSupporting contextReturned stateNot active

enc[i] ^ enc[i-1] wipes the shared k−1 bits, exposing s[i] and s[i-k].

Final result1011

C · Code with teaching comments

solution.javaJava

Telescoping Recurrence — Adjacent-Window Difference (Optimal) — optimal

4 teaching notes

1
public String cipher(int n, int k, String encoded) {
2
    char[] s = new char[n];
3
    int prev = encoded.charAt(0) - '0';
4
    s[0] = (char) ('0' + prev);              // first window is just s[0]
5
    for (int i = 1; i < n; i++) {
6
        int cur = encoded.charAt(i) - '0';
7
        int bit = cur ^ (encoded.charAt(i - 1) - '0');   // enc[i] ^ enc[i-1] = s[i] ^ s[i-k]
8
        // Only once i ≥ k has a bit (s[i-k]) actually left the window.
9
        if (i >= k) {
10
            bit ^= (s[i - k] - '0');         // remove the bit that left the window
11
        }
12
        s[i] = (char) ('0' + bit);
13
    }
14
    return new String(s);
15
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.15 lines

D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls6k = 1 — Window width 1 → enc == s. The recurrence gives s[i] = enc[i] ^ enc[i-1] ^ s[i-1] = enc[i], returning the input unchanged.Explore edge cases

Edge cases handled

k = 1Window width 1 → enc == s. The recurrence gives s[i] = enc[i] ^ enc[i-1] ^ s[i-1] = enc[i], returning the input unchanged.
n = 1Only s[0] = enc[0]; the loop never runs.
encoded = "1110100110", n = 7, k = 4Reconstructs "1001010", the canonical worked example.

Pitfalls

Using s[i-1] instead of enc[i-1] — breaks the cancellation identity from i = 2 onward.
Applying the s[i-k] term when i < k (no bit has left yet) and corrupting the early bits.
Reading enc[i-1] off the partially built s array rather than the original encoded string.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Using s[i-1] instead of enc[i-1]

The telescoping identity enc[i] ^ enc[i-1] = s[i] ^ s[i-k] holds for the ENCODED values. Swapping in the decoded s[i-1] breaks the cancellation and yields wrong bits from position 2 on.

Explore the code comparison

Don't write this

bit = int(encoded[i]) ^ s[i - 1]      # wrong: should be enc[i-1]
if i >= k: bit ^= s[i - k]

Write this instead

bit = int(encoded[i]) ^ int(encoded[i - 1])
if i >= k: bit ^= s[i - k]

Applying the leaving term too early

Before index k, the window hasn't dropped any bit, so there is no s[i-k] to remove. Adding it (or indexing s[i-k] with a negative index) corrupts the first bits.

Explore the code comparison

Don't write this

int bit = cur ^ (encoded.charAt(i - 1) - '0');
bit ^= (s[i - k] - '0');             // i-k can be negative when i < k

Write this instead

int bit = cur ^ (encoded.charAt(i - 1) - '0');
if (i >= k) bit ^= (s[i - k] - '0');

O(n·k) window recomputation

Re-XORing up to k−1 prior bits for every position is correct but quadratic-ish; at n, k = 10⁶ it's ~10¹² ops and times out. Telescope instead.

Explore the code comparison

Don't write this

for i in range(1, n):
    window = 0
    for j in range(max(0, i - k + 1), i):   # O(k) each
        window ^= s[j]
    s[i] = int(encoded[i]) ^ window

Write this instead

for i in range(1, n):
    bit = int(encoded[i]) ^ int(encoded[i - 1])
    if i >= k: bit ^= s[i - k]
    s[i] = bit

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Invert a sliding XOR window via adjacent-window difference

Code pattern to memorize

s[0] = enc[0]
for i in 1..n-1:
    s[i] = enc[i] ^ enc[i-1]
    if i >= k: s[i] ^= s[i-k]
# because enc[i] ^ enc[i-1] = s[i] ^ s[i-k]  (window shifted by one)

Rules to remember

1Encoding is a sliding XOR window of width k: enc[i] = s[i] ^ s[i-1] ^ … ^ s[i-k+1], with out-of-range s treated as 0. Encoded length is n + k − 1.
2Adjacent encoded bits differ by exactly the bit entering and the bit leaving the window: enc[i] ^ enc[i-1] = s[i] ^ s[i-k].
3Rearranged, s[i] = enc[i] ^ enc[i-1] ^ s[i-k], and the s[i-k] term only applies once i ≥ k (otherwise nothing has left the window yet).
4Seed with s[0] = enc[0] because the first window contains only s[0].
5Use enc[i-1], NOT s[i-1], in the recurrence — the cancellation identity is between consecutive ENCODED bits. Substituting s[i-1] is a common but wrong shortcut.

Use this pattern when

Decode/invert a stream produced by XOR over a sliding window
Telescoping: adjacent prefix/window values cancel to a tiny difference
Reconstruct a sequence from cumulative or windowed XOR sums
Any 'each output mixes the last k inputs by XOR' inversion

Choose another pattern when

The mixing op doesn't cancel on repeats (sum/product window) → need prefix arithmetic, not XOR cancellation
Window width isn't fixed / varies per position → the clean difference identity breaks
You need the encoder, not the decoder → just compute the windowed XOR forward
Encoded length doesn't equal n + k − 1 → re-derive the model before coding

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Flipping Bits
Another XOR-as-toggle problem — here a full-width complement via an all-ones mask.
Sansa and XOR
Also reasons about which contributions survive XOR over overlapping windows.
XOR Queries of a Subarray
Coming soon
Prefix-XOR telescoping: range XOR = prefix[r] ^ prefix[l-1], the same cancellation idea.

Same pattern

←

Sum vs XOR

Continue · Next problem

Counter Game