Problem Link : Prisoner of Azkaban
Author : Vikash Kumar Patel
Tester : Rishabh Sethi
Editorialist : Rohit Kumar
Pre-Requisite : DFS and similars, DSU
Problem : In this problem we need to create lexicographically smallest string from given string using m passes any number of times.In each pass two characters c1 and c2 are given and we can change any character c1 to c2 of the string.
Explanation : This problem can be solved by both DFS and similars and DSU. Here I will go with DFS.
For each pass we have directed edge from c1\space->c2. In the solution we will make a graph with all the edges reversed eg for c1->c2 it will be c2->c1 for all the passes. We also make an array which will store the corresponding changes for characters and is initialised with the the character’s own value.
Now start the DFS traversal with all nodes marked unvisited initially, starting from the vertex having smallest value and mark it as the parent of the larger vertices in the array while traversing and mark them visited.Finally, we will get the desired string after manipulating the original string according to the array.
Time Complexity : Time Complexity is O(n+m) .Time complexity for this question is very strict hence, fast Input/Output methods are recommended.
Setter Solution: link
