Полное решение: Давайте заметим, что если есть какое-то четное кол-во (-1), то в итоге все -1 превратятся в одну положительную единицу. Поэтому посчитаем все такие (-1), и просто возьмем их кол-во по модулю 2. Это и будет частью ответа. Дальше заметим, что если есть какое-то кол-во 0, то с ними мы ничего не сделаем, а значит второй частью ответа просто будет кол-во 0. Выведем наш ответ, как cnt1%2+cnt0, где cnt1 — кол-во -1, а cnt2 — кол-во 0. Сложность: O(n)

Полное решение: Т.к нам нужно максимизировать наш ответ, давайте просто возьмем самый максимальный элемент в пару со вторым максимальным, итд. Для этого можно просто отсортировать массив. Выведем наш ответ. Сложность: O(nlogn)

Полное решение: Давайте заметим, что если до требуемого k, нет какого-то числа, то нам не остается ничего, как просто добавить это число, так же если f(k)!=0, где f(x) — кол-во вхождений числа x в массив, то это число нужно заменить на какое-то другое тоже. Дальше стоит заметить, что вышеуказанные операции могут пересекаться, тогда ответом будет max(cnt,f(k)), где cnt — кол-во таких чисел от 0 до k, что вхождении в массив у этих элементов равна 0, т.е f(x) == 0. Выведем наш ответ. Сложность: O(n)

Полное решение: Допустим строка такая: ababaaba. Давайте просимулируем процесс для все b, для наглядности. i = 2, нам нужно посчитать кол-во сдвигов слева и справа, т.к слева нет букв б, то берем справа. bab = bba = 1 сдвиг. bbaaab = bbbaaa — 3 сдвига. Заметим, что для каждого b от 0 до і, число сдвигов до і это кол-во букв а от j до і, где j<i. Также для каждого b от і до n, число сдвигов до n, это кол-во букв от і до j, где j>=i. Тут можно заметить, что для каждого i, s[i] == 'b', сумма сдвигов считается как (Lefta — Righta)*p[i]+((sump[n-1]-sump[i-1])-sump[i-1]), где lefta — кол-во букв а от 0 до і-1, а rigtha — кол-во букв а от і до n, p[i] — кол-во букв б от 0 до і-1. Sump[i] — сумма всех p[i] таких индексов, что s[i]=='b'. Для буквы а делаем точно также, только уже с другими префиксами. Для большей наглядности можете просмотреть мой код. Сложность: O(n)

Полное решение: Сперва вспомним один из самых выжных лайфхаков связанное с работой на отрезках, а именно: Чтобы найти ответ для отрезка l — r, можно найти ответ для r, и отнять от него ответ для l-1. Теперь как использовать это для этой задачи? Давайте найдем колво отрезков с различными числами <=k, на отрезке от l — r, затем отнимем кол-во отрезков с различными числами <=k-1, на отрезке от l — r. Это и будет нашим ответом для данной задачи. P.S: Ответ мы можем находить с помощью двух указателей/ sliding window. Для большей ясности можете просмотреть мой код. Выведем наш ответ. Сложность: O(n)*4