Как далеко уйти, поправив маршрут

Средняя

Робот стоит в точке (0, 0) бесконечной клетчатой плоскости и по очереди выполняет команды строки route: N — на клетку вверх, S — вниз, E — вправо, W — влево. Перед стартом можно заменить не более edits символов маршрута на любые другие команды из этих четырёх. Верните наибольшее манхэттенское расстояние от начала координат, на котором робот может оказаться в какой-либо момент пути (не обязательно в конце). Манхэттенское расстояние до точки (x, y) равно |x| + |y|.

Пример 1

route="NENSW", edits=1 → 4

Меняем S на N: маршрут NENNW. После четвёртого шага мы в точке (1, 3), расстояние 4.

Пример 2

route="EWEW", edits=0 → 1

Без правок мы всё время качаемся между (0, 0) и (1, 0), дальше 1 не уйти.

Пример 3

route="SNSNWE", edits=2 → 5

Ограничения

1 ≤ len(route) ≤ 10⁵
0 ≤ edits ≤ len(route)
route состоит только из символов N, S, E, W

Встречал эту задачу на настоящем собесе?

Решили0

Пробовали0

Отправок0

Принято—

Темы

Hash Table Math String Counting

Вход

route="NENSW", edits=1

Ожидается

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 109 тестов на сервере, включая скрытые.