UNABLE-editorial

PROBLEM LINK:

Practice

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