Количество различных перестановок строки, полученной путем замены только неравных символов

Опубликовано: 21 Сентября, 2022

Для заданной строки найдите количество уникальных перестановок, которые можно получить, поменяв местами два индекса так, чтобы элементы с этими индексами были различны.

ПРИМЕЧАНИЕ. Обмен всегда выполняется в исходной строке.

Примеры:

Input: str = “sstt”
Output: 5
Explaination: 
Swap str[0] with str[2], string obtained “tsst” which is valid (str[0]!=str[2])
Swap str[0] with str[3]. string obtained “tsts”
Swap str[1] with str[2], string obtained “stst”
Swap str[1] with str[3], string obtained “stts”
Hence total 5 strings can be obtained including the given string (“sstt”)

Input: str = “abcd”
Output: 7

Подход: проблему можно решить с помощью HashMap, выполнив следующие шаги:

  1. Создайте хэш-карту и сохраните частоту каждого символа данной строки.
  2. Создайте переменную count для хранения общего количества символов в заданной строке, т.е. count=str.length() , и переменную ans для хранения количества возможных уникальных перестановок и инициализируйте ans=0.
  3. Пройдите по строке и для каждого символа:
    • Найдите количество различных символов, присутствующих справа от текущего индекса. Это можно сделать, вычитая частоту этого символа из общего количества.
    • Теперь добавьте это вычисленное значение к an , так как это количество символов, с которыми текущий символ можно поменять местами, чтобы создать уникальную перестановку.
    • Теперь уменьшите частоту текущего символа и подсчитайте на 1, чтобы он не мешал вычислениям тех же элементов, присутствующих справа от него.
  4. Возвратите ответ +1, потому что данная строка также является уникальной перестановкой.


Временная сложность: O(n)

Вспомогательное пространство: O(n)

РЕКОМЕНДУЕМЫЕ СТАТЬИ