Chef and his string challenge - TSECJ02 - Editorial

PROBLEM LINK:

Chef and his string challenge

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.