PROBLEM LINK:
Author: Arjun Bharat
Tester: Arjun Bharat
Editorialist: Arjun Bharat
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
Hashing, implementation
PROBLEM:
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.
QUICK EXPLANATION:
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).
EXPLANATION:
A sample snippet of the code used is shown below:
//Replacement operation coded in cpp14
for(i=1;i<=m;i++)
{
char p,q;
cin>>p>>q;
for(j=0;j<26;j++)
{
//a denotes the alphabet string, abcdefghijklmnopqrstuvwxyz
if(a[j]==p)
a[j]=q;
else if(a[j]==q)
a[j]=p;
}
for(i=0;i < n;i++)
printf("%c",a[message[i]-97]);
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.
ALTERNATIVE SOLUTION:
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