Author: Arjun Bharat
Tester: Arjun Bharat
Editorialist: Arjun Bharat
Given a string of length n consisting of only lowercase characters, subject to m pairwise character interchange operations, obtain the final state of the message.
It suffices to apply the interchange operation on the identity alphabet string, “abcdefghijklmnopqrstuvwxyz”.
This is because each original character of the alphabet is always mapped to the index corresponding to it’s ASCII value in the identity string(eg. c is mapped to ASCII©-97=index 2).
Thus replacement operations are O(m) and the final printing operation is O(n).
A sample snippet of the code used is shown below:
//Replacement operation coded in cpp14
//a denotes the alphabet string, abcdefghijklmnopqrstuvwxyz
for(i=0;i < n;i++)
To print the string we print the character at the index of it’s mapping in the alphabet string, since the index to which every character of the alphabet is mapped is an invariant.
Brute force would apply each interchange operation on the original string,which is O(nm) in overall complexity. This is not feasible given the program constraints.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here: jdoodle.com/a/wQx