Problema
Find the shortest contiguous substring of text that contains every character of pattern, including repeats. If several are equally short, return the leftmost.
Implement min_window(text, pattern).
Input
text: The text to search. pattern: The characters that must appear.
Output
Return the shortest window, or an empty string if none exists.
Restrições
1 ≤ length of text, pattern ≤ 100,000 (ASCII)
Exemplos
Entrada:
text = "ADOBECODEBANC"
pattern = "ABC"
Saída esperada:
expected = "BANC"Entrada:
std::string text = "ADOBECODEBANC";
std::string pattern = "ABC";
Saída esperada:
std::string expected = "BANC";Entrada:
string text = "ADOBECODEBANC";
string pattern = "ABC";
Saída esperada:
string expected = "BANC";Explicação
"BANC" contains A, B and C and nothing shorter does.
Entrada:
text = "a"
pattern = "aa"
Saída esperada:
expected = ""Entrada:
std::string text = "a";
std::string pattern = "aa";
Saída esperada:
std::string expected = "";Entrada:
string text = "a";
string pattern = "aa";
Saída esperada:
string expected = "";Explicação
Two a's are needed but the text has only one: "".
Como abordar
Tente sozinho primeiro e depois abra uma dica de cada vez.
Dica 1
A janela deve cobrir todas as contagens necessárias de caracteres, não apenas caracteres distintos.
Dica 2
Expanda até ficar válida, depois encolha pela esquerda para remover caracteres desnecessários sem perder a validade.
Dica 3
Se várias janelas tiverem o mesmo tamanho mínimo, mantenha a mais antiga ao atualizar a melhor resposta.
Complexidade esperada
tempo O(n), espaço extra O(1)
Referências
Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.