Преобразуйте заданные строки в T, заменяя символы между строками любое количество раз

Учитывая массив arr[] из N строк и строку T размера M , задача состоит в том, чтобы проверить, возможно ли сделать все строки в массиве arr[] такими же, как строка T , удалив любой символ из одной строки. , например, arr[i] и вставить его в любую позицию в другую строку arr[j] любое количество раз.

Примеры:

Input: arr[] = {“abc”, “abb”, “acc”}, T = “abc”
Output: Yes
Explanation:
Below is one of the possible way to make the all strings in the array to the string T is:

• Remove character at index 2 of the string arr[1](= “abb”) and then insert it at the index 1 of the string arr[2](= “acc”). After this the array modifies to {“abc”, “”ab”, “abcc”}.
• Remove character at index 3 of the string arr[2](= “abcc”) and then insert it at the index 2 of the string arr[1]( = “ab”). After this the array modifies to {“abc”, “”abc”, “abc”}.

After the above steps, all the strings of the array arr[] are equal to the string T(= abc). Therefore, print Yes.

Input: arr[] = {“abc”, “bbb”, “ccc”}, T = “abc”
Output: No

Подход: Данная проблема может быть решена на основе следующего наблюдения, что выход будет « Да » тогда и только тогда, когда выполняются следующие условия:

• None строка содержит какой-либо символ, которого нет в T .
• Все символы T должны присутствовать N раз во всех заданных строках S[] вместе взятых.

Следуйте инструкциям, чтобы решить проблему:

• Инициализируйте два массива, скажем, freqS[256] и freqT[256] со значением 0 , чтобы хранить частоту символов, присутствующих во всех строках массива, arr[] и строке T соответственно.
• Пройдите по заданному массиву строк arr[] и сохраните частоту символа для каждой строки в массиве freqS[] .
• Перебрать символы строки T и сохранить частоту символа строки T в массиве freqT[] .
• Выполните итерацию в диапазоне [0, 255], используя переменную i , и выполните следующие шаги:
  • Если значение freqS[i] и freqT[i] равно 0 или значение freqS[i] равно N*freq[T] , то продолжаем итерацию.
  • В противном случае инициализируйте логическую переменную, скажите A как истину и прервите цикл.
• После выполнения вышеуказанных шагов, если значение A истинно, выведите «No» . В противном случае выведите « Да ».

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

Временная сложность: O(N*L + M), где L — длина самой длинной строки в массиве arr[].
Вспомогательное пространство: O(26)