В этом посте мы обсудим, как решить проблему с минимальной оконной подстрокой, используя принцип скользящего окна.

Описание проблемы:

Для строки S и строки T найдите минимальное окно в S, которое будет содержать все символы из T со сложностью O (n).

Пример:

Ввод: S = «ADOBECODEBANC», T = «ABC».

Выход: «БАНК»

Примечание. Если в S нет такого окна, которое покрывает все символы в T, верните пустую строку «».

Если такое окно есть, гарантируется, что в S. всегда будет только одно уникальное минимальное окно.

Пошаговое решение проблемы:

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

Базовый случай:

если s или t равны нулю, мы не можем найти между ними общего окна.

if(s==null || t==null) return “”;

Основной алгоритм:

сначала давайте сохраним все количество символов t на карте, как показано ниже, чтобы мы могли легко проверить доступность персонажа с этой карты в O (1).

int[] map=new int[128]; 
for(Character c:t.toCharArray())map[c]++;

Давайте возьмем два указателя start и end для итерации по s и инициализируем их 0 вместе с некоторыми другими переменными.

int start = 0, end = 0, minStart = 0, minLen = Integer.MAX_VALUE, counter = t.length();

Теперь мы перебираем s, используя конечный указатель, и проверяем, присутствует ли текущий символ в t или нет, проверяя map [arr [end]] ›0. Если он присутствует, уменьшаем значение счетчика, чтобы указать, что он у нас есть. соответствие символа и символ (count-1), который необходимо сопоставить. Также мы уменьшаем map [arr [end]], чтобы указать, что мы прошли текущий символ, используя конечный указатель.

В этом процессе, если мы получаем count == 0, это означает, что мы получили желаемое окно, поэтому замените это окно как окно результата, если это минимальное окно.

Теперь мы увеличиваем map [arr [start]], чтобы восстановить счетчик символов на карте и обозначать, что мы закончили с arr [start], и перемещаем start указатель вперед, чтобы удалить начало из текущего окна.

Здесь следует отметить две важные вещи:

1. if (map[arr[end]] > 0) counter — ;
   end++;

это означает, что мы получили совпадение char в s с char в t, поэтому у нас есть counter-1 char для сопоставления в текущем окне.

2. if(map[arr[start]]>0)counter++;
   start++;

это означает, что после восстановления фактического счетчика символов в карте путем перехода через указатель начала, если счетчик> 0, тогда счетчик увеличивается и начинается, поскольку мы удаляем этот символ из текущего окна и перемещаем окно вперед.

Полный код этой проблемы можно найти в https://github.com/GyanTech877/algorithms/blob/master/slidingwindow/SlidingWindowMaximum.java.

Удачного обучения 😎