Loading…

easyStrings0Sometimes asked

Mars Exploration

Q: How do you solve Mars Exploration using the Build the Expected String, Then Compare (Naive) approach?

When to use it: Mention to show the comparison clearly, then point out the template string is unnecessary. The literal approach materialises the message the probe *meant* to send, then diffs it against what arrived. **Why it is natural.** The problem describes the original as '"SOS" repeated', so you build exactly that: `"SOS".repeat(n / 3)`. Then a parallel walk over both strings counts mismatches. The logic is transparent and obviously correct. **Why it wastes space.** You allocated a brand-new `O(n)` string whose contents are completely predictable — it's `S, O, S, S, O, S, …`. Storing a pattern you can regenerate from the index alone is redundant. For `n = 10⁴` it's harmless, but it signals you missed that the template is a pure function of position. **The realisation.** The expected character at index `i` is `"SOS"[i % 3]`. Once you see that, the second string evaporates — you compare each received character against a three-element lookup, in place, with no allocation. Time complexity: O(n). Space complexity: O(n).

Q: How do you solve Mars Exploration using the Index Modulo 3 In Place (Optimal) approach?

When to use it: The intended answer. Phrase it as 'the expected letter at i is "SOS"[i % 3]; count mismatches'. Walk the received string and, at each index, compare the character to its expected counterpart `"SOS"[i % 3]`. Count the mismatches. **Why `i % 3` gives the expected letter.** The original message is the block `"SOS"` laid end to end. The character at global index `i` sits at position `i % 3` *inside* its block — remainder `0` is the first 'S', remainder `1` is the 'O', remainder `2` is the second 'S'. So the expected letter is exactly `"SOS"[i % 3]`, computed in constant time without ever storing the full template. **Why this is a Hamming distance.** Both the received and expected strings have identical length and alignment (no insertions or deletions, only in-place alterations). The number of altered letters is therefore the count of positions where they disagree — the textbook definition of Hamming distance. We compute it on the fly against the periodic template. **Why the length being a multiple of 3 matters.** It guarantees the message is whole 'SOS' blocks, so `i % 3` cycles cleanly S→O→S→S→O→S with no ragged final block to special-case. Every index maps to a well-defined expected letter. **Why O(1) space.** The expected character is regenerated from `i` each step, so there is no second string — just the three-character constant `"SOS"` and an integer counter. Memory use is independent of the input length. Time complexity: O(n). Space complexity: O(1).

Arrays & Hashing · 33 of 83 · 5 min

A probe on Mars sends the message "SOS" repeated, but cosmic interference may have altered some letters during transmission. You receive a string s whose length is a multiple of 3, formed from the original "SOS" repeated |s| / 3 times.

Return the number of letters that were altered — i.e. the number of positions in s that differ from the expected repeated "SOS" pattern.

In plain English

The original transmission is rigidly periodic: S, O, S, S, O, S, …. Each received character should match the expected one for its position. Wherever it doesn't, a letter was altered in transit. Counting those positions gives the number of changes — there's no ambiguity about what 'should' be there because the template is fixed.

Examples

Example 1

Input: s = "SOSSPSSQSSOR"
Output: 3
Note: Expected SOSSOSSOSSOS. Differences at index 4 (P vs O), 7 (Q vs O), 11 (R vs S) → 3 altered letters.

Example 2

Input: s = "SOSSOT"
Output: 1
Note: Expected SOSSOS. Only index 5 differs (T vs S) → 1.

Example 3

Input: s = "SOSSOS"
Output: 0
Note: Matches the template exactly — nothing was altered.

Constraints

1 ≤ |s| ≤ 10⁴
|s| is divisible by 3
s consists of uppercase English letters only
The original message is "SOS" repeated |s| / 3 times

Clarifying questions4First question: Is the length always a multiple of 3?Explore questions

Q1.Is the length always a multiple of 3?
Yes — the message is whole 'SOS' blocks. That guarantees i % 3 cycles cleanly through S, O, S without a partial block.
Q2.Could entire 'SOS' blocks be inserted or deleted, shifting alignment?
No. Only individual letters are altered in place; alignment is preserved, so a position-by-position comparison is valid.
Q3.Do I return the count or the positions of the changes?
Just the count of altered letters, which is why we never need to record where they are.
Q4.Are letters always uppercase?
Yes, the alphabet is uppercase, and the template letters 'S' and 'O' are uppercase too — no case handling needed.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

The intended message is "SOS" repeated, so the expected character at index i is just "SOS"[i % 3]. Walk the received string once and count every position whose letter differs from that expected character. That count is the number of altered letters. O(n) time, O(1) space.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you recognise the expected message is periodic and index it with i % 3, computing a Hamming-style mismatch count in one pass without building the template string.

Where candidates slip

Constructing the full expected "SOS" repetition and comparing two strings — correct but uses O(n) extra space when i % 3 needs none.

How to stand out

State that this is a Hamming distance against the periodic template "SOS", note the input length is always a multiple of 3, and use i % 3 to pick the expected character in place.

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	Build the Expected String, Then Compare (Naive)	`O(n)`	`O(n)`	Mention to show the comparison clearly, then point out the template string is unnecessary.	Read
2	Index Modulo 3 In Place (Optimal)Optimal	`O(n)`	`O(1)`	The intended answer. Phrase it as 'the expected letter at i is "SOS"[i % 3]; count mismatches'.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewreceived sscan i = 0 .. n-1YesNoExplore 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

Build the Expected String, Then Compare (Naive)

TimeO(n)SpaceO(n)

Mention to show the comparison clearly, then point out the template string is unnecessary.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Construct the expected message: "SOS" repeated |s| / 3 times.

2Hint 2Explore hint

Compare it to s character by character and count the positions that differ.

3Hint 3Explore hint

It works — but you allocated a second string of the same size. Can you know the expected character without storing it?

A · Core idea

The literal approach materialises the message the probe meant to send, then diffs it against what arrived.

Why it is natural. The problem describes the original as '"SOS" repeated', so you build exactly that: "SOS".repeat(n / 3). Then a parallel walk over both strings counts mismatches. The logic is transparent and obviously correct.

Why it wastes space. You allocated a brand-new O(n) string whose contents are completely predictable — it's S, O, S, S, O, S, …. Storing a pattern you can regenerate from the index alone is redundant. For n = 10⁴ it's harmless, but it signals you missed that the template is a pure function of position.

The realisation. The expected character at index i is "SOS"[i % 3]. Once you see that, the second string evaporates — you compare each received character against a three-element lookup, in place, with no allocation.

B · Visual dry run

Interactive dry run

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

s = "SOSSOT"

Build

"SOS" × 2

Stateexpected = "SOSSOS"

Final result1

C · Code with teaching comments

Reference implementation previewpublic int marsExploration(String s) { String expected = "SOS".repeat(s.length() / 3); int changed = 0; for (int i = 0; i < s.length(); i++) { if (s.charAt(i) != expected.charAt(i)) {Explore the full code

solution.javaJava

Build the Expected String, Then Compare (Naive) — reference

2 teaching notes

1
public int marsExploration(String s) {
2
    // Materialise the whole expected message — an O(n) allocation we don't actually
3
    // need.
4
    String expected = "SOS".repeat(s.length() / 3);
5
    int changed = 0;
6
    for (int i = 0; i < s.length(); i++) {
7
        // Count positions where received and expected differ.
8
        if (s.charAt(i) != expected.charAt(i)) {
9
            changed++;
10
        }
11
    }
12
    return changed;
13
}

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

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

Any time you build a string that is fully determined by index (a constant repeated, an arithmetic pattern), you can usually replace it with an O(1) formula on the index — here, "SOS"[i % 3].

ComplexityO(n) time, O(n) space — Building the expected string is O(n) time and O(n) space; comparing the two strings is another O(n) pass. Asymptotically fine on time, wasteful on space.

E · Edge cases and pitfalls3Allocating an O(n) template you can derive from i % 3.Explore edge cases

Pitfalls

Allocating an O(n) template you can derive from i % 3.
Repeating by the wrong count (n/3, not n) so lengths mismatch.
Comparing with the wrong index if you build the template lazily and lose alignment.

03.2

Approach 2 of 2 · Optimal

Index Modulo 3 In Place (Optimal)

TimeO(n)SpaceO(1)

The intended answer. Phrase it as 'the expected letter at i is "SOS"[i % 3]; count mismatches'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The expected message repeats every 3 characters. What's the expected character at index i in terms of i and the block "SOS"?

2Hint 2Explore hint

Position i within its block is i % 3, so the expected letter is "SOS"[i % 3]: 'S','O','S' for remainders 0,1,2.

3Hint 3Explore hint

Scan once; whenever s[i] differs from "SOS"[i % 3], increment a counter. No template string, O(1) space.

A · Core idea

Walk the received string and, at each index, compare the character to its expected counterpart "SOS"[i % 3]. Count the mismatches.

Why `i % 3` gives the expected letter. The original message is the block "SOS" laid end to end. The character at global index i sits at position i % 3 inside its block — remainder 0 is the first 'S', remainder 1 is the 'O', remainder 2 is the second 'S'. So the expected letter is exactly "SOS"[i % 3], computed in constant time without ever storing the full template.

Why this is a Hamming distance. Both the received and expected strings have identical length and alignment (no insertions or deletions, only in-place alterations). The number of altered letters is therefore the count of positions where they disagree — the textbook definition of Hamming distance. We compute it on the fly against the periodic template.

Why the length being a multiple of 3 matters. It guarantees the message is whole 'SOS' blocks, so i % 3 cycles cleanly S→O→S→S→O→S with no ragged final block to special-case. Every index maps to a well-defined expected letter.

Why O(1) space. The expected character is regenerated from i each step, so there is no second string — just the three-character constant "SOS" and an integer counter. Memory use is independent of the input length.

B · Visual dry run

Interactive dry run

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

s = "SOSSPSSQSSOR"

Array state

i=4

'P' vs expected 'O' → altered

[0]

[1]

[2]

[3]

i ↓

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

Current pointerResolved stateNot processed

Final result3

C · Code with teaching comments

solution.javaJava

Index Modulo 3 In Place (Optimal) — optimal

3 teaching notes

1
public int marsExploration(String s) {
2
    // The three-character template; we index it by i % 3 instead of repeating it.
3
    String sos = "SOS";
4
    int changed = 0;
5
    for (int i = 0; i < s.length(); i++) {
6
        // Expected letter for position i is sos[i % 3] — a constant-time lookup, no
7
        // allocation.
8
        if (s.charAt(i) != sos.charAt(i % 3)) {
9
            // Each mismatch is one altered letter; this is the Hamming distance.
10
            changed++;
11
        }
12
    }
13
    return changed;
14
}

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

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

Comparing against a periodic template is just template[i % period]. Recognising the expected value as a function of the index turns an O(n)-space string diff into an O(1)-space counting loop — the same move you'd make for any repeating pattern.

ComplexityO(n) time, O(1) space — A single pass with constant work per character (one modulo, one array index, one comparison) is O(n) time. Only a counter is stored → O(1) extra space.

E · Edge cases and pitfalls6s = "SOS" — Single block matching the template → 0 altered.Explore edge cases

Edge cases handled

s = "SOS"Single block matching the template → 0 altered.
s = "OOO"Expected S,O,S → indices 0 and 2 differ → 2 altered.
s = "SOSSOSSOS"Three perfect blocks → 0.

Pitfalls

Using a fixed expected character instead of cycling with i % 3.
Indexing the template with i instead of i % 3 (out of bounds past position 2).
Assuming alignment could shift — only in-place letter changes occur, so position-wise compare is valid.

Practice

Try the solution yourself

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

Editable code previewpublic int marsExploration(String s) { String sos = "SOS"; int changed = 0; for (int i = 0; i < s.length(); i++) { if (s.charAt(i) != sos.charAt(i % 3)) {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.

Indexing the template by i, not i % 3

The template has only 3 characters; using the raw index i runs off the end after position 2.

Explore the code comparison

Don't write this

if (s.charAt(i) != "SOS".charAt(i)) changed++;

Write this instead

if (s.charAt(i) != "SOS".charAt(i % 3)) changed++;

Comparing every position to 'S'

Positions with remainder 1 should be 'O'. Comparing all positions to 'S' falsely flags every correct 'O' and misses altered 'O's.

Explore the code comparison

Don't write this

return sum(1 for c in s if c != 'S')

Write this instead

sos = "SOS"
return sum(1 for i, c in enumerate(s) if c != sos[i % 3])

Allocating the expected string needlessly

The expected message is fully determined by the index, so storing a copy wastes O(n) memory for no benefit.

Explore the code comparison

Don't write this

expected = "SOS" * (len(s) // 3)
return sum(a != b for a, b in zip(s, expected))

Write this instead

sos = "SOS"
return sum(1 for i, c in enumerate(s) if c != sos[i % 3])

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Compare against a periodic template via index % 3

Code pattern to memorize

changed = 0
for i in 0 .. n-1:
    if s[i] != "SOS"[i % 3]:
        changed += 1
return changed

Rules to remember

1The expected letter at position i is "SOS"[i % 3] — index 0,3,6… expect 'S'; 1,4,7… expect 'O'; 2,5,8… expect 'S'.
2Length is always a multiple of 3 (whole 'SOS' blocks), so i % 3 cleanly cycles S-O-S.
3Don't build the expected "SOS"×(n/3) string — compare against "SOS"[i % 3] in place for O(1) space.
4Equivalently: within each 3-block, position 0 and 2 must be 'S', position 1 must be 'O'. The modulo encodes exactly that.
5Count mismatches; never try to 'correct' the string — you only report how many letters changed.

Use this pattern when

Compare a received/observed sequence against a known periodic template
The expected value at each index is a simple function of i (here i % period)
You only need a count of differences (a Hamming-style distance)
The template repeats, so you can index it modulo its period

Choose another pattern when

The template isn't periodic → precompute or stream the expected values instead
You must output the corrected string → still O(n) but you build output
Differences are weighted or positional cost varies → simple count is insufficient
Alignment/shift is unknown → this becomes string matching, not index-wise compare

Interview takeaway

When you compare against a repeating template, the expected element at index i is template[i % period]. Counting index-wise mismatches is a Hamming distance — no need to materialise the template or correct anything.

Continue

Transfer the pattern to another problem

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

Transferable patternHamming distance against a periodic template. When the expected value at index i is template[i % period], you can count mismatches in one pass with O(1) space — never materialise the template. Generalises to any repeating reference pattern.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Hamming distance between two strings
Coming soon
Same count-of-mismatches idea, but compare against a second given string instead of a template.
Count alterations against an arbitrary periodic pattern
Coming soon
Generalise "SOS" to any pattern p; expected char is p[i % len(p)].
Repair the message (output the corrected string)
Coming soon
Now emit "SOS"[i % 3] wherever it differs — the build-output variant.
Count the Number of Consistent Strings
Coming soon
Another per-character template-matching count over a fixed reference.

Same pattern

←

Counting Valleys

Continue · Next problem

Sherlock and Anagrams

easyStrings0Sometimes asked

Mars Exploration

Arrays & Hashing · 33 of 83 · 5 min

Return the number of letters that were altered — i.e. the number of positions in s that differ from the expected repeated "SOS" pattern.

In plain English

Examples

Example 1

Input: s = "SOSSPSSQSSOR"
Output: 3
Note: Expected SOSSOSSOSSOS. Differences at index 4 (P vs O), 7 (Q vs O), 11 (R vs S) → 3 altered letters.

Example 2

Input: s = "SOSSOT"
Output: 1
Note: Expected SOSSOS. Only index 5 differs (T vs S) → 1.

Example 3

Input: s = "SOSSOS"
Output: 0
Note: Matches the template exactly — nothing was altered.

Constraints

1 ≤ |s| ≤ 10⁴
|s| is divisible by 3
s consists of uppercase English letters only
The original message is "SOS" repeated |s| / 3 times

Clarifying questions4First question: Is the length always a multiple of 3?Explore questions

Q1.Is the length always a multiple of 3?
Yes — the message is whole 'SOS' blocks. That guarantees i % 3 cycles cleanly through S, O, S without a partial block.
Q2.Could entire 'SOS' blocks be inserted or deleted, shifting alignment?
No. Only individual letters are altered in place; alignment is preserved, so a position-by-position comparison is valid.
Q3.Do I return the count or the positions of the changes?
Just the count of altered letters, which is why we never need to record where they are.
Q4.Are letters always uppercase?
Yes, the alphabet is uppercase, and the template letters 'S' and 'O' are uppercase too — no case handling needed.

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 recognise the expected message is periodic and index it with i % 3, computing a Hamming-style mismatch count in one pass without building the template string.

Where candidates slip

Constructing the full expected "SOS" repetition and comparing two strings — correct but uses O(n) extra space when i % 3 needs none.

How to stand out

State that this is a Hamming distance against the periodic template "SOS", note the input length is always a multiple of 3, and use i % 3 to pick the expected character in place.

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	Build the Expected String, Then Compare (Naive)	`O(n)`	`O(n)`	Mention to show the comparison clearly, then point out the template string is unnecessary.	Read
2	Index Modulo 3 In Place (Optimal)Optimal	`O(n)`	`O(1)`	The intended answer. Phrase it as 'the expected letter at i is "SOS"[i % 3]; count mismatches'.	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

Build the Expected String, Then Compare (Naive)

TimeO(n)SpaceO(n)

Mention to show the comparison clearly, then point out the template string is unnecessary.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Construct the expected message: "SOS" repeated |s| / 3 times.

2Hint 2Explore hint

Compare it to s character by character and count the positions that differ.

3Hint 3Explore hint

It works — but you allocated a second string of the same size. Can you know the expected character without storing it?

A · Core idea

The literal approach materialises the message the probe meant to send, then diffs it against what arrived.

B · Visual dry run

Interactive dry run

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

s = "SOSSOT"

Build

"SOS" × 2

Stateexpected = "SOSSOS"

Final result1

C · Code with teaching comments

solution.javaJava

Build the Expected String, Then Compare (Naive) — reference

2 teaching notes

1
public int marsExploration(String s) {
2
    // Materialise the whole expected message — an O(n) allocation we don't actually
3
    // need.
4
    String expected = "SOS".repeat(s.length() / 3);
5
    int changed = 0;
6
    for (int i = 0; i < s.length(); i++) {
7
        // Count positions where received and expected differ.
8
        if (s.charAt(i) != expected.charAt(i)) {
9
            changed++;
10
        }
11
    }
12
    return changed;
13
}

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

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

Any time you build a string that is fully determined by index (a constant repeated, an arithmetic pattern), you can usually replace it with an O(1) formula on the index — here, "SOS"[i % 3].

ComplexityO(n) time, O(n) space — Building the expected string is O(n) time and O(n) space; comparing the two strings is another O(n) pass. Asymptotically fine on time, wasteful on space.

E · Edge cases and pitfalls3Allocating an O(n) template you can derive from i % 3.Explore edge cases

Pitfalls

Allocating an O(n) template you can derive from i % 3.
Repeating by the wrong count (n/3, not n) so lengths mismatch.
Comparing with the wrong index if you build the template lazily and lose alignment.

03.2

Approach 2 of 2 · Optimal

Index Modulo 3 In Place (Optimal)

TimeO(n)SpaceO(1)

The intended answer. Phrase it as 'the expected letter at i is "SOS"[i % 3]; count mismatches'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The expected message repeats every 3 characters. What's the expected character at index i in terms of i and the block "SOS"?

2Hint 2Explore hint

Position i within its block is i % 3, so the expected letter is "SOS"[i % 3]: 'S','O','S' for remainders 0,1,2.

3Hint 3Explore hint

Scan once; whenever s[i] differs from "SOS"[i % 3], increment a counter. No template string, O(1) space.

A · Core idea

Walk the received string and, at each index, compare the character to its expected counterpart "SOS"[i % 3]. Count the mismatches.

B · Visual dry run

Interactive dry run

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

s = "SOSSPSSQSSOR"

Array state

i=4

'P' vs expected 'O' → altered

[0]

[1]

[2]

[3]

i ↓

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

Current pointerResolved stateNot processed

Final result3

C · Code with teaching comments

solution.javaJava

Index Modulo 3 In Place (Optimal) — optimal

3 teaching notes

1
public int marsExploration(String s) {
2
    // The three-character template; we index it by i % 3 instead of repeating it.
3
    String sos = "SOS";
4
    int changed = 0;
5
    for (int i = 0; i < s.length(); i++) {
6
        // Expected letter for position i is sos[i % 3] — a constant-time lookup, no
7
        // allocation.
8
        if (s.charAt(i) != sos.charAt(i % 3)) {
9
            // Each mismatch is one altered letter; this is the Hamming distance.
10
            changed++;
11
        }
12
    }
13
    return changed;
14
}

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

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

ComplexityO(n) time, O(1) space — A single pass with constant work per character (one modulo, one array index, one comparison) is O(n) time. Only a counter is stored → O(1) extra space.

E · Edge cases and pitfalls6s = "SOS" — Single block matching the template → 0 altered.Explore edge cases

Edge cases handled

s = "SOS"Single block matching the template → 0 altered.
s = "OOO"Expected S,O,S → indices 0 and 2 differ → 2 altered.
s = "SOSSOSSOS"Three perfect blocks → 0.

Pitfalls

Using a fixed expected character instead of cycling with i % 3.
Indexing the template with i instead of i % 3 (out of bounds past position 2).
Assuming alignment could shift — only in-place letter changes occur, so position-wise compare is valid.

Practice

Try the solution yourself

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

Editable code previewpublic int marsExploration(String s) { String sos = "SOS"; int changed = 0; for (int i = 0; i < s.length(); i++) { if (s.charAt(i) != sos.charAt(i % 3)) {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.

Indexing the template by i, not i % 3

The template has only 3 characters; using the raw index i runs off the end after position 2.

Explore the code comparison

Don't write this

if (s.charAt(i) != "SOS".charAt(i)) changed++;

Write this instead

if (s.charAt(i) != "SOS".charAt(i % 3)) changed++;

Comparing every position to 'S'

Positions with remainder 1 should be 'O'. Comparing all positions to 'S' falsely flags every correct 'O' and misses altered 'O's.

Explore the code comparison

Don't write this

return sum(1 for c in s if c != 'S')

Write this instead

sos = "SOS"
return sum(1 for i, c in enumerate(s) if c != sos[i % 3])

Allocating the expected string needlessly

The expected message is fully determined by the index, so storing a copy wastes O(n) memory for no benefit.

Explore the code comparison

Don't write this

expected = "SOS" * (len(s) // 3)
return sum(a != b for a, b in zip(s, expected))

Write this instead

sos = "SOS"
return sum(1 for i, c in enumerate(s) if c != sos[i % 3])

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Compare against a periodic template via index % 3

Code pattern to memorize

changed = 0
for i in 0 .. n-1:
    if s[i] != "SOS"[i % 3]:
        changed += 1
return changed

Rules to remember

1The expected letter at position i is "SOS"[i % 3] — index 0,3,6… expect 'S'; 1,4,7… expect 'O'; 2,5,8… expect 'S'.
2Length is always a multiple of 3 (whole 'SOS' blocks), so i % 3 cleanly cycles S-O-S.
3Don't build the expected "SOS"×(n/3) string — compare against "SOS"[i % 3] in place for O(1) space.
4Equivalently: within each 3-block, position 0 and 2 must be 'S', position 1 must be 'O'. The modulo encodes exactly that.
5Count mismatches; never try to 'correct' the string — you only report how many letters changed.

Use this pattern when

Compare a received/observed sequence against a known periodic template
The expected value at each index is a simple function of i (here i % period)
You only need a count of differences (a Hamming-style distance)
The template repeats, so you can index it modulo its period

Choose another pattern when

The template isn't periodic → precompute or stream the expected values instead
You must output the corrected string → still O(n) but you build output
Differences are weighted or positional cost varies → simple count is insufficient
Alignment/shift is unknown → this becomes string matching, not index-wise compare

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

Hamming distance between two strings
Coming soon
Same count-of-mismatches idea, but compare against a second given string instead of a template.
Count alterations against an arbitrary periodic pattern
Coming soon
Generalise "SOS" to any pattern p; expected char is p[i % len(p)].
Repair the message (output the corrected string)
Coming soon
Now emit "SOS"[i % 3] wherever it differs — the build-output variant.
Count the Number of Consistent Strings
Coming soon
Another per-character template-matching count over a fixed reference.

Same pattern

←

Counting Valleys

Continue · Next problem

Sherlock and Anagrams