Попробую решить на 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;
}