Genome Mutation Time

Reconstruction Note

This is a reconstructed version of the Amazon online assessment problem commonly referred to as “Genome Mutation Time”, based on multiple independent public descriptions of the same question. Wording and explicit constraints may differ slightly from the original internal statement, but the core logic, examples, and required output are consistent across sources.[1][2][3][4]

---

Problem Description

Data scientists at Amazon are working on sequencing the genome of a microorganism. A genome is the complete set of DNA instructions, where each DNA strand is composed of various nucleotides represented as characters in a string.[3]

They have discovered a particular mutated nucleotide (always the same character, e.g., 'm' or 'z') that removes nucleotides to its left over time. The behavior is as follows:[2][3]

• Time progresses in discrete units: 1, 2, 3, ...
• In one unit of time, every occurrence of the mutated nucleotide in the current genome string simultaneously removes exactly one nucleotide immediately to its left, if such a nucleotide exists.
• The mutated nucleotide can remove any nucleotide to its left, including:
  • a normal (non-mutated) nucleotide, or
  • another mutated nucleotide.
• When a mutated nucleotide to the right removes a mutated nucleotide to its left, the left one is deleted from the string. In this sense, the mutation can “remove itself” via another mutated nucleotide.

Formally, at each time step:

• Consider the current genome string from left to right.
• For every index i such that genome[i] == mutation:
  • If i - 1 >= 0, then the nucleotide at index i - 1 is marked for deletion.
• After all such indices are considered, all marked nucleotides are removed simultaneously, and the string compacts to close the gaps.
• Then the next time unit begins with this new string.

You are given:

• a string genome denoting the current genome of the organism, and
• a character mutation denoting the mutated nucleotide.

Your task is to compute the earliest time (in integer units) after which no further removals are possible. Equivalently, this is the smallest non‑negative integer t such that after performing the above removal process for t time steps, there is no occurrence of the mutated nucleotide that has any nucleotide immediately to its left (so in the next time step, nothing would be removed).[2][3]

• If the mutation character does not appear in the genome at all, then no nucleotide is ever removed, and the required time is 0.[4]
• The genome is not required to become empty; the process stops as soon as no mutated nucleotide has a left neighbor it can remove.

---

Input/Output Format

The original OA is given as a function to implement. A natural abstraction consistent with public descriptions is:[3][4][2]

text int genomeMutationTime(string genome, char mutation)

• Input

  • genome: a non-empty string representing the nucleotides in the organism’s genome.
    • Characters: lowercase English letters 'a'–'z'.
    • Each character corresponds to some nucleotide.
  • mutation: a single lowercase English letter representing the mutated nucleotide.

• Output

  • An integer representing the earliest time (number of time units) after which no further removals are possible under the described process.

For platforms that use standard input for custom testing (as in some descriptions):

• STDIN
  • One line with the genome string, e.g., genome = 'tamem'
  • One line with the mutation character, e.g., mutation = 'm'
• STDOUT
  • A single integer: the required time.

---

Examples

Example 1

Input

text genome = "tamem" mutation = 'm'

Output

text 2

Explanation

Initial genome: "tamem"
Indices: 0:'t', 1:'a', 2:'m', 3:'e', 4:'m'

Time unit 1:

• Mutated nucleotide at index 2 ('m') removes the left neighbor at index 1 ('a').
• Mutated nucleotide at index 4 ('m') removes the left neighbor at index 3 ('e').

Both removals happen simultaneously, so after deleting indices 1 and 3, the remaining characters are:

• index 0:'t', index 2:'m', index 4:'m' → new genome "tmm"

Now indices are re-labeled: 0:'t', 1:'m', 2:'m'.

Time unit 2:

• Mutated nucleotide at index 1 ('m') removes index 0 ('t').
• Mutated nucleotide at index 2 ('m') removes index 1 ('m').

Again, deletions are simultaneous; indices 0 and 1 are removed, leaving only the last 'm'. New genome: "m".

At this point, the single remaining mutated nucleotide has no left neighbor, so no further removals are possible. Thus, the earliest time after which no more removals can occur is 2.

---

Example 2

Input

text genome = "luvzliz" mutation = 'z'

Output

text 3

Explanation

Initial genome: "luvzliz"
Indices: 0:'l', 1:'u', 2:'v', 3:'z', 4:'l', 5:'i', 6:'z'[2]

Time unit 1:

• 'z' at index 3 removes index 2 ('v').
• 'z' at index 6 removes index 5 ('i').

After removing these indices, the remaining characters in order are:

• indices 0:'l', 1:'u', 3:'z', 4:'l', 6:'z' → "luzlz"

Relabel indices: 0:'l', 1:'u', 2:'z', 3:'l', 4:'z'.

Time unit 2:

• 'z' at index 2 removes index 1 ('u').
• 'z' at index 4 removes index 3 ('l').

After removal: indices 0:'l', 2:'z', 4:'z' → "lzz"

Relabel indices: 0:'l', 1:'z', 2:'z'.

Time unit 3:

• 'z' at index 1 removes index 0 ('l').
• 'z' at index 2 removes index 1 ('z').

After removal, only one 'z' remains. New genome: "z".

Now the only mutated nucleotide has no left neighbor, so no further removals are possible. The earliest time after which no removals can occur is 3.

---

Example 3

Input

text genome = "aa" mutation = 'a'

Output

text 1

Explanation

Initial genome: "aa"
Indices: 0:'a', 1:'a' (both are the mutated nucleotide).

Time unit 1:

• 'a' at index 1 removes index 0 ('a').
• 'a' at index 0 has no left neighbor, so it removes nothing.

After simultaneous deletion, only one 'a' remains. New genome: "a".

Now this remaining 'a' has no left neighbor, so no more removals can happen. The earliest time after which no removals are possible is 1.[3]

---

Constraints

From publicly available versions of this problem, only qualitative constraints are explicitly given; precise numeric limits (like maximum string length) are not specified. The following are the constraints and behavioral rules that are clear from the descriptions:[4][2][3]

• genome is a non-empty string.
• genome consists of lowercase English letters only.
• mutation is a single lowercase English letter.
• If mutation does not occur in genome, the answer is 0 (no removals ever occur).
• All removals in a given time unit are performed simultaneously based on the positions at the start of that time unit.
• The process can continue for multiple time units until reaching a configuration where no mutated nucleotide has a left neighbor; at that point, the answer is the number of time units elapsed.
• The intended solution must efficiently handle large inputs (typical Amazon OA scale), so an algorithm with linear time complexity in the length of genome and constant or linear extra space is expected, rather than step-by-step simulation for every time unit.

---

Solution Hint

Observe that each mutated nucleotide effectively “eats” one character to its left per time unit, and can also consume earlier mutated nucleotides; the time when deletions stop is governed by how far the rightmost mutated nucleotides need to reach to clear everything to their left. You can solve this in one pass by tracking the positions of the mutation character and taking a simple greedy maximum over the distance from the start to the first mutation and the gaps between consecutive mutations, without explicitly simulating each time step.