Проверить, совпадают ли подпоследовательности, образованные заданными символами, для запросов Q

Учитывая массив arr[] из N строк и Q запросов, каждый из которых содержит некоторые символы, задача состоит в том, чтобы проверить, для каждого запроса подпоследовательности из всех строк состоят только из всех вхождений символов этого запроса. одинаковые или нет.

A subsequence is a sequence that can be derived from the given sequence by deleting some or no elements without changing the order of the remaining elements. 

Примеры:

Input: arr[] = {“accbad”, “abcacd”, “cacbda”}, queries[] = {{‘a’}, {‘a’, ‘b’}, {‘a’, ‘d’}, {‘b’, ‘c’, ‘d’}, {‘a’, ‘b’, ‘d’}
Output: 
True
True
False
True
False
False
Explanation: All strings generate the subsequence “aa” using only the character ‘a’.
All strings generate subsequence “aba” using only the characters ‘a’ and ‘b’.
arr[1] and arr[2] generate subsequence “aad”, but arr[3] generates subsequence “ada” using only the characters ‘a’ and ‘d’, and since subsequences don’t match, false is printed.
All strings generate the subsequence “bd” using only the characters ‘b’ and ‘d’
arr[1] and arr[3] generate subsequence “ccbd”, but arr[2] generates subsequence “bccd” using only the characters ‘b’, ‘c’, and ‘d’, so print ‘False’.
arr[1] and arr[2] generate subsequence “abad”, but arr[3] generates subsequence “abda” using only the characters ‘a’, ‘b’, and ‘d’

Input: arr[] = {“adacb”, “aacbd”}, queries[] = {{‘a’, ‘b’, ‘c’}}
Output: True.
Explanation: The subsequences are ‘aacb’ for both the strings

Наивный подход: для каждого запроса сгенерируйте подпоследовательности, содержащие все вхождения всех символов этого запроса, и проверьте, совпадают ли они или нет.

Временная сложность: O(Q * N * M), где M — средняя длина каждой строки.
Вспомогательное пространство: O(1)

Эффективный подход с использованием мемоизации. Эту проблему можно эффективно решить, основываясь на следующей идее:

If the relative positions of all the characters for a query are the same in all the strings then the subsequence is common in all of them.

The relative positions of any character (say character ch), can be find out by finding the frequencies of all the characters of a query upto the index of ch. If they are the same then their relative position are also same.

Следуйте шагам, указанным ниже, чтобы реализовать идею:

• Создайте трехмерный (скажем, elements[] ) массив для хранения частоты каждого символа строк до каждого индекса.
• Пройдите все строки, найдите частоту и сохраните их.
• Теперь проверьте относительное расположение символов запроса.
• Чтобы реализовать это эффективно, выполните итерацию по массиву строк, сравните соседние строки и выполните следующие действия:
  • Найдите относительное положение каждого символа по отношению к любому другому символу в английском алфавите (относительное положение проверяется путем проверки частоты всех других символов до этого индекса).
  • Если они не совпадают для символа (например, ch ) в двух строках, добавьте символы, вызывающие несоответствие, в набор . (несоответствие означает, что количество частот не совпадает)
  • Проверьте, совпадают ли найденные несоответствия с символами запроса.
  • Если это так, то образованные подпоследовательности не совпадают. Так что верните false .
• После того, как итерация завершена и «ложь» не возвращена, сформированные подпоследовательности одинаковы.

Следуйте иллюстрации ниже для лучшего понимания.

Иллюстрация:

Say arr[] = {“adacb”, “aacbd”}, queries[] = {{‘a’, ‘b’, ‘c’}}

The frequencies of all the characters for arr[0] and arr[1] are shown below

arr[0] = 

	‘a’	‘d’	‘a’	‘c’	‘b’
a	1	1	2	2	2
b	0	0	0	0	1
c	0	0	0	1	1
d	0	1	1	1	1

arr[1] = 

	‘a’	‘a’	‘c’	‘b’	‘d’
a	1	2	2	2	2
b	0	0	0	1	1
c	0	0	1	1	1
d	0	0	0	0	1

For ‘a’:
        => The relative positions of the second ‘a’ are not same.
        => In the first string there is an extra ‘d’ before the 2nd ‘a’.
        => So the mismatch set is { ‘d’ }.

For ‘b’:
        => The relative positions of ‘b’ are not same.
        => In the first string there is an extra ‘d’ before it.
        => So the mismatch set is { ‘d’ }.

For ‘c’:
        => The relative positions of ‘c’ are not same.
        => In the first string there is an extra ‘d’ before it.
        => So the mismatch set is { ‘d’ }.

Now no mismatch set contains the same character as the ones present in the query. So the subsequence formed is the same for the strings.

Ниже приведена реализация описанного выше подхода.

Временная сложность: O(C ² * N + Q * N)
Вспомогательное пространство: O(C ² * N), где C = 26