Количество различных групп строк, сформированных после выполнения эквивалентной операции

Дан массив arr[] из N строк, состоящих из строчных букв, задача состоит в том, чтобы найти количество различных групп строк, образованных после выполнения эквивалентной операции.

Two strings are said to be equivalent if there exists the same character in both the strings and if there exists another string that is equivalent to one of the strings in the group of equivalent string then that string is also equivalent to that group.

Примеры:

Input: arr[] = {“a”, “b”, “ab”, “d”}
Output: 2
Explanation:
As strings “b” and “ab” have ‘b’ as the same character, they are equivalent also “ab” and  the string”a” have ‘a’ as the same character, so the strings “a”, “b”, “ab” are equivalent and “d” is another string.

Therefore, the count of distinct group of strings formed is 2.

Input: arr[] = {“ab”, “bc”, “abc”}
Output: 1

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

• Инициализируйте векторы parent(27), rank(27, 0), total(26, false) и current(26, false) .
• Инициализируйте переменную, скажем, distCount как 0 , которая хранит количество различных строк.
• Переберите диапазон [0, 27), используя переменную i , и установите значение parent[i] как i .
• Переберите диапазон [0, N), используя переменную i , и выполните следующие шаги:
  • Переберите диапазон [0, 26), используя переменную j , и установите для current[j] значение false .
  • Перебрать символы строки arr[i] с помощью переменной ch и установить для current[ch – 'a'] значение true .
  • Переберите диапазон [0, 26), используя переменную j , и, если current[j] истинно, установите total[j] в true и вызовите функцию Union(parent, rank, arr[i][0] – 'a ', к) .
• Переберите диапазон [0, 26), используя переменную i , и проверьте, является ли значение total[i] истинным , а Find(parent, i) равно I , если оно истинно, а затем увеличьте значение distCount на 1 .
• Наконец, выведите значение distCount .

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

Временная сложность: O(N*log N), так как мы используем цикл для прохождения N раз, а функция объединения будет стоить нам logN времени.
Вспомогательное пространство: O(1), так как мы используем постоянное пространство размером 27.