Подсчитайте способы разбить строку на два подмножества, противоположные друг другу

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

Примеры:

Input: S = “cabaacba”
Output: 4
Explanation:
Below are the ways of partitioning the string satisfying the given conditions:

1. Take the characters at the indices {0, 4, 6, 7} as the first subset and the remaining characters as the second subset. Then the string formed are “caba” and “abac” and the second string is the reverse of the first string.
2. Take the characters at the indices {0, 3, 6, 7} as the first subset and remaining characters as the second subset. Then the string formed are “caba” and “abac” and the second string is the reverse of the first string.
3. Take the characters at the indices {1, 2, 3, 5} as first subset and remaining characters as the second subset. Then the string formed are “abac” and “caba” and the second string is the reverse of first string.
4. Take the characters at the indices {1, 2, 4, 5} as first subset and remaining characters as the second subset. Then the string formed are “abac” and “caba” and the second string is the reverse of the first string.

Therefore, the number of ways of splitting is 4.

Input: N = 11, S = “mippiisssisssiipsspiim”
Output: 504

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

• Инициализируйте переменную, скажем , как 0 , чтобы сохранить общее количество способов разделения строки.
• Переберите диапазон [0, 2 ^N ], используя переменную маску, и выполните следующие шаги:
  • Инициализируйте две строки, скажем, X и Y , чтобы сохранить символы первого подмножества и второго подмножества.
  • Переберите диапазон [0, N] и, если i ^-й бит установлен в целочисленной маске , добавьте символ S[i] к X . В противном случае добавьте символ S[i] к Y .
  • Переверните строку Y , а затем проверьте, равна ли первая строка X второй строке Y , а затем увеличьте an на 1 .
• После выполнения вышеуказанных шагов выведите значение ans как общее количество способов.

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

Временная сложность: O(N* ^2N )
Вспомогательное пространство: O(N)