Разделить строку на две подстроки, имеющие максимальное количество общих неповторяющихся символов

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

Примеры:

Input : str = “aabbca” 
Output: 2 
Explanation: 
Partition the string into two substrings { { str[0], … str[2] }, { str[3], …, str[5] } } 
The common non-repeating characters present in both the substrings are { ‘a’, ‘b’} 
Therefore, the required output is 2.

Input: str = “aaaaaaaaaa” 
Output: 1

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

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

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

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

• Инициализируйте переменную, скажем, res , для хранения максимального количества общих различных символов, присутствующих в обеих подстроках, путем разделения строки на две подстроки.
• Инициализируйте карту, скажем, mp , чтобы хранить частоту каждого отдельного символа строки.
• Инициализируйте упорядоченный набор, скажем, Q , чтобы хранить отдельные символы строки в отсортированном порядке.
• Перебрать символы строки и для каждого i ^-го символа уменьшить частоту str[i] и проверить, равна ли частота mp[str[i]] 0 или нет. Если окажется ложным, удалите str[i] из Ordered Set .
• В противном случае вставьте str[i] в упорядоченный набор и обновите res = max(res, X) , где X — количество элементов в упорядоченном наборе.
• Наконец, выведите значение res .

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

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