Яндекс.Контест - Wrong-Answer на третьем тесте

Рейтинг: 2Ответов: 2Опубликовано: 17.02.2023

Решаю задачу по алгоритмам на Яндекс.Контесте.

Условие задачи

Красотой строки назовем максимальное число идущих подряд одинаковых букв. (красота строки abcaabdddettq равна 3)

Сделайте данную вам строку как можно более красивой, если вы можете сделать не более k операций замены символа.

Формат ввода. Первая строка положительный int k. Вторая строка String непустая строка.

Формат вывода Выведите одно число — максимально возможную красоту строчки, которую можно получить.

Примеры:

Ввод  
2 
abcaz 

Вывод 
4
Ввод  
2 
helto 

Вывод 
3

В IDEA получаю ожидаемый результат, но на сайте не проходит последний тест. В чем причина того, что последний тест не проходит?

Код решения на Java:

import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.Path;
import java.util.Comparator;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;

public class Main {
    public static void main(String[] args) throws IOException {
        List<String> list = Files.readAllLines(Path.of("input.txt"));
        int count = Integer.parseInt(list.get(0));
        String word = list.get(1);
        Map<Character, Integer> map = new TreeMap<>();
        for (char ch : word.toCharArray()) {
            if (!map.containsKey(ch)) {
                map.put(ch, 0);
            }
            map.put(ch, map.get(ch) + 1);
        }
        int maxCharCount = map.entrySet()
            .stream()
            .max(Map.Entry.comparingByValue))
            .get().getValue();
        int result = maxCharCount + count;
        if (result >= word.length()) {
            result = word.length();
        }
        System.out.println(result);
    }
}

Ответы

▲ 4Принят

Думаю, задачу можно решить с использованием метода двух указателей (индексов).

Ставим left и right в 0, и начинаем двигать правый индекс. На каждом шаге модифицируем мап, аналогичный тому, что вы уже сделали, увеличивая счетчик для текущего символа. Как только количество "побочных" символов в окне превысит количество замен, останавливаемся, сравниваем величину окна (разность right-left) с максимально достигнутой.

Теперь двигаем левый индекс, на каждом шаге уменьшая счетчик для уходящего из окна символа. Как только количество "побочных символов" в окне станет равно количеству замен, останавливаемся.

Повторяем процедуру.

Побочные символы - все, кроме символа с максимальным счетчиком

▲ 1

Небольшое дополнение к замечательному ответу @MBo - https://ru.stackoverflow.com/a/1497134/551745

Решаем методом динамического плавающего окна через два итератора.

  1. Мы должны считать не просто побочные символы, а считать именно их сумму, так как побочные символы могут быть разбросаны в разном количестве внутри окна
  2. Чтобы найти побочные символы внутри окна, необходимо так же найти и символ с максимальными символами внутри текущего окна

Напишу на котлине, но думаю принцип вы поймете и на джаве:

fun beautyOfString(s: String, k: Int): Int {
    val frequencyMap = mutableMapOf<Char, Int>(s.first() to 1)
    var left = 0
    var window = 1

    for (right in 1 until s.length) {
        frequencyMap.computeIfPresent(s[right]) { _, frequency -> frequency + 1 }
        frequencyMap.putIfAbsent(s[right], 1)

        val mostFrequentChar = frequencyMap.maxByOrNull { it.value }!!.key
        var additionalElementsCount = frequencyMap.values.sum() - frequencyMap[mostFrequentChar]!!

        while (left != right && additionalElementsCount > k) {
            frequencyMap.computeIfPresent(s[left]) { _, frequency -> frequency - 1 }
            if (frequencyMap[s[left]] == 0) frequencyMap.remove(s[left])
            additionalElementsCount--
            left++
        }

        window = maxOf(window, right - left + 1)
    }

    return window
}