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.
Vincoli
1 ≤ length of text, pattern ≤ 100,000 (ASCII)
Esempi
Input:
text = "ADOBECODEBANC"
pattern = "ABC"
Output atteso:
expected = "BANC"Input:
std::string text = "ADOBECODEBANC";
std::string pattern = "ABC";
Output atteso:
std::string expected = "BANC";Input:
string text = "ADOBECODEBANC";
string pattern = "ABC";
Output atteso:
string expected = "BANC";Spiegazione
"BANC" contains A, B and C and nothing shorter does.
Input:
text = "a"
pattern = "aa"
Output atteso:
expected = ""Input:
std::string text = "a";
std::string pattern = "aa";
Output atteso:
std::string expected = "";Input:
string text = "a";
string pattern = "aa";
Output atteso:
string expected = "";Spiegazione
Two a's are needed but the text has only one: "".
Come affrontarlo
Prova prima da solo, poi apri un suggerimento alla volta.
Suggerimento 1
La finestra deve coprire tutti i conteggi richiesti dei caratteri, non solo i caratteri distinti.
Suggerimento 2
Espandi finché è valida, poi restringi da sinistra per rimuovere i caratteri non necessari restando valida.
Suggerimento 3
Se più finestre hanno la stessa lunghezza minima, conserva la prima quando aggiorni la migliore risposta.
Complessità attesa
tempo O(n), spazio aggiuntivo O(1)
Riferimenti
Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.