Минимальные операции, при которых каждый заданный сегмент String имеет разные символы

Дана строка S длины N , диапазоны Q формы [L, R] в диапазоне двумерного массива и перестановка arr[] , содержащая числа от 1 до N . За одну операцию вы можете удалить первый неудаленный символ в соответствии с перестановкой. Однако позиции других персонажей не изменятся. Определите минимальное количество операций, удовлетворяющих следующим условиям:

• Все символы в каждом из диапазонов Q различны. Удаленные символы не учитываются.
• Считается, что диапазон, в котором удалены все символы, содержит все отдельные символы.
• Последовательность из n целых чисел называется перестановкой, если она содержит все целые числа от 1 до n ровно один раз.

Примечание: используется индексация на основе 1.

Примеры:

Input: N = 5, Q = 2, S = “aaaaa”, arr[] = {2, 4, 1, 3, 5}, ranges = {{1, 2}, {4, 5}}
Output: 2
Explanation: After the first operation, the string becomes a_aaa
After the second operation, the string becomes a_a_a
Now, in both ranges, all characters are distinct.
Hence, the output is 2.

Input: N = 8, Q = 3, S = “abbabaab”, arr[] = {6, 3, 5, 1, 4, 2, 7, 8}, ranges = {{1, 3}, {4, 7}, {3, 5}}
Output: 5
Explanation: After the first operation, the string becomes abbab_ab
After the second operation, the string becomes ab_ab_ab
After the third operation, the string becomes ab_a_ _ab
After the fourth operation, the string becomes _b_a_ _ab
After the fifth operation, the string becomes _b_ _ _ _ab
Now, in all the ranges, all characters are distinct.
Hence, the output is 5.

Подход: Чтобы решить проблему, следуйте следующей идее:

One easy way is to traverse the permutation and remove characters serially. At each traversal, we will traverse each query to find whether they all contain unique characters. If the answer comes to be positive then return the number of traversals is the final answer.

Выполните следующие шаги, чтобы решить проблему:

• Если все запросы имеют уникальные символы, верните 0 .
• Пройдите перестановку arr[] от i = 0 до N-1 :
  • Инициализируйте (arr[i] — 1)-й индекс с помощью '_' в списке temp и вызовите isValid .
  • Внутри функции isValid :
    • Пройдитесь по диапазонам запроса, используя итератор j .
      • Если temp[j] != '_', то поместите temp[j] в массив (скажем, ss ).
      • Если длина набора, сформированного ss , не равна длине ss , то есть повторяющиеся символы, поэтому верните False .
      • В противном случае верните True .
  • Если isValid возвращает True , верните i+1 в качестве окончательного ответа.
  • В противном случае верните -1 .

Ниже приведена реализация описанного выше подхода.

Временная сложность: O(N * Q * M), где M — максимальный диапазон
Вспомогательное пространство: O(N)