Feature #5: Mutating a Virus
Explore how to determine the most potent mutation of an alien virus's DNA by finding its next lexicographically greater nucleotide sequence. Understand the step-by-step approach to rearranging nucleotides in place, ensuring optimal time and space efficiency, and apply this knowledge to computational biology problems.
We'll cover the following...
Description
Suppose that the DNA of a virus from an alien species consists of 10 different nucleotides, which are represented by the numbers, 0 through 9. It mutates by transforming itself into a different permutation of the same nucleotides. A mutant with the next lexicographically greater permutation of nucleotides is most likely to survive. This is referred to as the most potent mutation of the virus. Once it has mutated to the lexicographically highest possible permutation, it rearranges its nucleotides to the lowest possible permutation.
In this problem, we are given a sequence of nucleotides. To get the next greater sequence of nucleotides, we have to rearrange the nucleotides into their next lexicographically high permutation. If such an arrangement is not possible, the nucleotides must be rearranged to the lowest possible permutation.
Note: We need to ensure that the replacement is in place and uses constant extra memory.
Given its current DNA sequence, our task is to find the DNA sequence for the most potent mutant of a virus.
The following examples clarify these requirements:
Solution
Observe that no other higher permutation is possible if the sequence of nucleotides is in descending order. For example, no higher permutation is ...