Last active
October 11, 2023 21:09
-
-
Save guisantos/154c9986e7df82b445fe7d4e1aa84f2e to your computer and use it in GitHub Desktop.
Minimum Window Substring in C#
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| var s = "ADOBZASQWECCCODEBANCNMKLNJNCBA"; | |
| var substring = "ABC"; | |
| Console.WriteLine(MinWindow(s, substring)); | |
| string MinWindow(string s, string substring) | |
| { | |
| var subsDictionary = new Dictionary<char, int>(); | |
| var window = new Dictionary<char, int>(); | |
| var matches = 0; | |
| var need = substring.Length; | |
| var currentSolutionStart = 0; | |
| var solutionLength = 0; | |
| var left = 0; | |
| foreach (var letter in substring) | |
| { | |
| if (subsDictionary.ContainsKey(letter)) | |
| { | |
| subsDictionary[letter] += 1; | |
| } | |
| else | |
| { | |
| subsDictionary.Add(letter, 1); | |
| window.Add(letter, 0); | |
| } | |
| } | |
| for (int right = 0; right < s.Length; right++) | |
| { | |
| var c = s[right]; | |
| if (window.ContainsKey(c)) | |
| { | |
| window[c] += 1; | |
| if (window[c] == subsDictionary[c]) | |
| { | |
| matches++; | |
| } | |
| while (matches == need) | |
| { | |
| if (right - left + 1 < solutionLength || solutionLength == 0) | |
| { | |
| solutionLength = right - left + 1; | |
| currentSolutionStart = left; | |
| } | |
| if (window.ContainsKey(s[left])) | |
| { | |
| window[s[left]] -= 1; | |
| if (window[s[left]] < subsDictionary[s[left]]) | |
| { | |
| matches--; | |
| } | |
| } | |
| left++; | |
| } | |
| } | |
| } | |
| if (solutionLength == 0) | |
| { | |
| return ""; | |
| } | |
| return s.Substring(currentSolutionStart, solutionLength); | |
| } | |
| //credits: https://www.youtube.com/watch?v=jSto0O4AJbM |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment