PROBLEM LINK:
Author: Aniket Marlapalle
Tester: Devamanyu Hazarika
Editorialist: Saumyajit Dey
DIFFICULTY:
EASY-MEDIUM.
PREREQUISITES:
graph, dfs
PROBLEM:
Given a string with partially filled characters. Also mentioned the pairs that should have same character. Print the number of ways to fill the remaining characters of the string such that the condition stated is not violated.
EXPLANATION:
In this problem you have to find the no of ways to fill the question marks with characters so that the given constraints are followed. Now according to the constraints build a graph.
Now every connected component in the graph should have the same character. So we have 3 cases here:
Case 1:
If there is exactly one character present in the connected component and we have at
least one question mark then no of ways to fill this component will be m.
Case 2:
If there is exactly one character present in the connected component and we don’t have any question mark then no of ways to fill this component will be 1.
Case 3:
If there are more than one characters in the component then answer will be -1.
Now total answer will be the product of answer of all the connected components.
AUTHOR’S AND TESTER’S SOLUTIONS:
Tester’s solution can be found here.