PROBLEM LINK:
Author: Himanshu
Editorialist: Yogesh Malpani
DIFFICULTY:
EASY.
PREREQUISITES:
String, Map
PROBLEM:
Given n queries consisting of a single integer m_i, task is to find whether there exists a contiguous substring q of p such that all letters of q are the same and product of value of that letter v and length of the substring |q| is equal to m_i, that is, v * |q| = mi
EXPLANATION:
If we find all the possible contiguous substrings q of p and save the product of their value with their lengths as values in a dictionary, we can perform a lookup in our dictionary for each query (which ends up being much faster than certain other data structures).
To do this, we’ll first need to find all contiguous substrings; this means we must iterate through each letter in string p and create a dictionary entry for each of them.
If query n_i exists in the dictionary, print Yes; otherwise, print No to indicate n_i was not found in the dictonary.
CHALLENGE YOURSELF:
Can you answer the queries accurately without determining every single uniform substring’s weight beforehand?
AUTHOR’S SOLUTION:
Author’s solution can be found here.