Find the Smallest Window in String s that Contains?

All Characters of String t

string MinWindow(string s, string t)

if (string.IsNullOrEmpty(s) || string.IsNullOrEmpty(t)) return

"";

Dictionary<char, int> dictT = new Dictionary<char, int>();

foreach (char c in t)

dictT[c] = dictT.ContainsKey(c) ? dictT[c] + 1 : 1;

int required = dictT.Count;

int formed = 0;

Dictionary<char, int> windowCounts = new Dictionary<char,

int>();

int left = 0, right = 0;

int minLen = int.MaxValue, minLeft = 0;

while (right < s.Length)

char c = s[right];

windowCounts[c] = windowCounts.ContainsKey(c) ?

windowCounts[c] + 1 : 1;

if (dictT.ContainsKey(c) && windowCounts[c] == dictT[c])

formed++;

while (left <= right && formed == required)

if (right - left + 1 < minLen)

minLen = right - left + 1;

Follow on:

minLeft = left;

char leftChar = s[left];

windowCounts[leftChar]--;

if (dictT.ContainsKey(leftChar) &&

windowCounts[leftChar] < dictT[leftChar])

formed--;

left++;

right++;

return minLen == int.MaxValue ? "" : s.Substring(minLeft,

minLen);

Explanation:

Sliding window with two pointers keeps track of counts of chars matching the target.