Как можно оптимизировать код в данной задаче? Не проходит по времени, использую алгоритм двух указателей
Красотой строки назовем максимальное число идущих подряд одинаковых букв. (красота строки abcaabdddettq равна 3)
Сделайте данную вам строку как можно более красивой, если вы можете сделать не более k операций замены символа.
Формат ввода
В первой строке записано одно целое число k (0 ≤ k ≤ 109)Во второй строке дана непустая строчка S (|S| ≤ 2 ⋅ 105). Строчка S состоит только из маленьких латинских букв.
Формат вывода
Выведите одно число — максимально возможную красоту строчки, которую можно получить.
k = int(input())
s = str(input())
mass = list(set(s))
j = 0
for bukva in mass:
left = 0
right = 0
count = 0
while left != len(s) - 1:
while right != len(s) - 1 and (s[right] == bukva or count != k):
if s[right] != bukva:
count += 1
right += 1
j = max(j, right - left)
if s[left] != bukva:
count -= 1
left += 1
print(j)
Ответы (3 шт):
Попробую решить на C#
Итак, что вы делаете: вы начинаете слева и от него двигаете праввый указатель каждую итерацию Это значит, что при длине строки N вы в худшем случае выполните O(N**2) (N в степени 2) операций.
Квадратичный алгоритм конечно не очень эффективно. Но! у нас есть один хинт в задании - все символы - это английский алфавит в нижнем регисре. То есть, по сути, в строке 26 разных символов повторяются.
Таким образом, если вы решим задачу для одного сивола линейно, то запустив её 26 раз, у нас общая сложность остается линейной.
Пример, давайте пройдемся по символам и для каждого решим подзадачу
int MaxBeauty(string s, int k)
{
int max = 0;
for(char c='a'; c<='z'; c++){
max = Math.Max(max, MaxBeauty(s, k, c));
}
return max;
}
Функию выше можно оптимизмровать, если заранее посчитать какие символы использованы в строке и только по ним пройтись. Оставим это как домашку.
Теперь решение для одного символа, которое тоже работает на 2 указателях, но при этом за линейное время.
int MaxBeauty(string s, int k, char c)
{
int left = 0;
int right = 0;
int nonMath = 0;
int max = 0;
while(left < s.Length)
{
while(right < s.Length && nonMath <= k)
{
if (s[right] != c)
{
nonMath++;
}
right++;
if (nonMath > k)
{
nonMath--;
right--;
break;
}
}
max = Math.Max(max, right - left);
if (s[left] != c) nonMath--;
left ++;
}
return max;
}
Как видно из функции выше, я просто ищу максимальное окно в строке, где не-символов c не более, чем k.
Если бы вы поделились тестами своими, я бы их проверил, а так приходится самому придумывать =)
Проверка.
Console.WriteLine(MaxBeauty("aaabbbaaa", 2));
Console.WriteLine(MaxBeauty("aaabbbaaa", 3));
Console.WriteLine(MaxBeauty("aaababaaa", 2));
Console.WriteLine(MaxBeauty("baaababaaab", 2));
Вывод
5
9
9
9
UPD Пример с небольшими улучшениями, просто отсекаем ненужные вычисления. Кардинально ничего не улучшает, просто небольшие оптимизации.
Например, имеет смысл начать с самых часто встречающихся букв, и если следующая буква даже с учетом замен не превысит максимум - нет смысла её обсчитывать.
int MaxBeauty(string s, int k)
{
int max = 0;
var counters = new Dictionary<char, int>();
foreach (var c in s)
{
if (counters.ContainsKey(c)) counters[c]++;
else counters.Add(c, 1);
}
foreach (var kv in counters.OrderByDescending(z=>z.Value))
{
if (kv.Value + k < max) continue;
max = Math.Max(max, MaxBeauty(s, k, kv.Key, max));
}
return max;
}
Ну и тут можно передавать текущий максимум и если уже никаких шансов его превысить.
int MaxBeauty(string s, int k, char c, int max)
{
int left = 0;
int right = 0;
int nonMath = 0;
while (left < s.Length)
{
if (left + max > s.Length) return max;
while (right < s.Length && nonMath <= k)
{
if (s[right] != c)
{
nonMath++;
}
right++;
if (nonMath > k)
{
nonMath--;
right--;
break;
}
}
max = Math.Max(max, right - left);
if (s[left] != c) nonMath--;
left++;
}
return max;
}
Ещё вариант решения за линейное время (в общем случае(n*Alphabet_Size)), быстрый (~0.08 с для длины 100000):
def longestseqwithkrepl(s, k):
n = len(s)
cc = [0]*26
cmax = 0
left = 0
right = -1
mx = -1
while right < n - 1:
while right < n-1:
right += 1
ch = ord(s[right])-97
cc[ch] += 1
if cmax < cc[ch]:
cmax = cc[ch]
if right - left + 1 - cmax > k:
break
else:
mx = max(mx, right - left + 1)
while left < right:
ch = ord(s[left])-97
cc[ch] -= 1
if cc[ch] + 1 == cmax:
cmax = max(cc)
left += 1
if right - left + 1 - cmax <= k:
break
return mx
Старый вариант с Counter (медленнее):
from collections import Counter
k = 3
s = "acaaabbaaccaa"
n = len(s)
c = Counter()
left = 0
right = -1
mx = -1
while right < n - 1:
while right < n-1:
right += 1
c[s[right]] += 1
t = c.most_common(1)[0][1]
if right - left + 1 - t > k:
break
else:
mx = max(mx, right - left + 1)
while left < right:
c[s[left]] -= 1
left += 1
t = c.most_common(1)[0][1]
if right - left + 1 - t <= k:
break
print(mx)
NB Простое и самое быстрое решение ищите в ответе MBo. Здесь вы найдёте другое решение, у которого лучшая асимптотика, но которое на практике в два раза медленнее. Константы рулят!
Сложность решения в вопросе - len(s) * len(set(s)). Второй множитель не превосходит 26 - число букв латиницы. Хотя множитель не большой, из-за него Питону не хватает времени. Для ускорения пригодится счётчик со следующим интерфейсом:
Counter() # создать пустой счётчик; Counter.inc(c) # увеличить на единицу счётчик для символа c; Counter.dec(c) # уменьшить на единицу счётчик для символа c; Counter.get_max() # вернуть значение максимального счётчика.
Со счётчиком решение задачи выглядит так:
def beauties(k, s):
c = Counter()
i = 0
for j, v in enumerate(s):
c.inc(v)
while k + c.get_max() < j - i + 1:
c.dec(s[i])
i += 1
yield j - i + 1
Это генератор, который для каждой позиции j возвращает максимальную длину k-красивой строки с концом в j. Из всех длин надо выбрать максимум.
Counter устроен как куча (пирамида). Рядом с собственно кучей хранится словарь указывающий положения символов в куче. Куча и словарь меняются согласованно. Нулевые счётчики из кучи исключаются.
Сложность операции c.get_max - константная, операций c.inc, c.dec - логарифмическая от объёма счётчика (26 символов). В худшем случае требуется пять операций, в среднем меньше одной - чаще всего порядок элементов в куче не меняется. Сложность алгоритма в целом - len(s) * log(len(set(s))). В сравнении с оригинальным алгоритмом второй множитель попал под логарифм.
Всё вместе:
class Counter:
def __init__(self):
self._heap = []
self._index = {}
def inc(self, key):
if key in self._index:
i = self._index[key]
else:
i = len(self._heap)
self._index[key] = i
self._heap.append([0, key])
self._heap[i][0] += 1
self._sift_up(i)
def dec(self, key):
i = self._index[key]
if self._heap[i][0] > 1:
self._heap[i][0] -= 1
self._sift_down(i)
else:
j = len(self._heap) - 1
assert self._heap[i][0] <= self._heap[j][0]
self._swap(i, j)
self._heap.pop()
del self._index[key]
if i < len(self._heap):
self._sift_up(i)
def get_max(self):
return self._heap[0][0]
def _swap(self, i, j):
self._heap[i], self._heap[j] = self._heap[j], self._heap[i]
self._index[self._heap[j][1]] = j
self._index[self._heap[i][1]] = i
def _sift_up(self, i):
while i > 0:
j = (i - 1) // 2 # parent
if self._heap[j][0] >= self._heap[i][0]:
break
self._swap(j, i)
i = j
def _sift_down(self, i):
while True:
k = i # greatest value index
j = 2 * i + 1 # left child
if j < len(self._heap) and self._heap[k][0] < self._heap[j][0]:
k = j
j += 1 # right child
if j < len(self._heap) and self._heap[k][0] < self._heap[j][0]:
k = j
if k == i:
break
self._swap(i, k)
i = k
def beauties(k, s):
c = Counter()
i = 0
for j, v in enumerate(s):
c.inc(v)
while k + c.get_max() < j - i + 1:
c.dec(s[i])
i += 1
yield j - i + 1
print(max(beauties(int(input()), input()), default=0))
На больших примерах куча быстрее перебора символов в пятнадцать раз. Возможно, этого хватит - проверить я не могу.