Количество суперстрок в заданном массиве строк

Учитывая 2 массива строк X и Y , задача состоит в том, чтобы найти количество суперстрок в X.

A string s is said to be a Superstring, if each string present in array Y is a subsequence of string s .

Примеры:

Input: X = {“ceo”, “alco”, “caaeio”, “ceai”}, Y = {“ec”, “oc”, “ceo”}
Output: 2
Explanation: Strings “ceo” and “caaeio” are superstrings as each string of array Y is a subset of these 2 strings. Other strings are not included in answer all strings of array Y are not 
sub-sets of them.

Input: X = {“iopo”, “oaai”, “iipo”}, Y = {“oo”}
Output: 1

Подход: Идея состоит в том, чтобы использовать концепцию хеширования для хранения частот символов для решения проблемы. Выполните следующие шаги, чтобы решить проблему:

• Инициализируйте массив размером 26, чтобы сохранить максимальное количество вхождений каждого символа [az] в каждой строке, присутствующей в массиве Y .
• Теперь рассмотрим каждую строку s в X,
  • Проверьте, превышает ли частота каждого символа в s частоту, полученную на предыдущем шаге.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N*N1 + M*M1), где N = размер массива X, N1 = Maxlength(x), M = размер массива Y, M1 = Maxlength(y),

Сложность пространства: O(1)