Skip to content

Commit d0998ad

Browse files
quickmquickm
committed
Added class and test method for code challenge Minimum Window Substring.
1 parent 31e48e4 commit d0998ad

File tree

5 files changed

+147
-1
lines changed

5 files changed

+147
-1
lines changed

‎Coderbyte_CSharp/Coderbyte_CSharp.csproj

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -52,6 +52,7 @@
5252
<Compile Include="Medium Challenges\ConsecutiveNumbers.cs" />
5353
<Compile Include="Medium Challenges\NumberEncoder.cs" />
5454
<Compile Include="Medium Challenges\PrimeNumber.cs" />
55+
<Compile Include="Medium Challenges\StringMinimumWindow.cs" />
5556
<Compile Include="Medium Challenges\StringUniqueSubstring.cs" />
5657
<Compile Include="Program.cs" />
5758
<Compile Include="Properties\AssemblyInfo.cs" />

‎Coderbyte_CSharp/Medium Challenges/MediumChallenges.txt

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -10,4 +10,4 @@ Run Length
1010
String Reduction
1111
Symmetric Tree
1212
Tree Constructor
13-
Minimum Window Substring
13+
Minimum Window Substring 02/12/2021 StringMinimumWindow

‎Coderbyte_CSharp/Medium Challenges/StringMinimumWindow.cs

Lines changed: 118 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,118 @@
1+
using System;
2+
using System.Collections.Generic;
3+
using System.Linq;
4+
using System.Text;
5+
using System.Threading.Tasks;
6+
7+
namespace Coderbyte_CSharp.Medium_Challenges
8+
{
9+
class StringMinimumWindow
10+
{
11+
// Have the function MinWindowSubstring(strArr) take the array of strings stored
12+
// in strArr, which will contain only two strings, the first parameter being the
13+
// string N and the second parameter being a string K of some characters, and your
14+
// goal is to determine the smallest substring of N that contains all the characters
15+
// in K.
16+
//
17+
// For example: if strArr is ["aaabaaddae", "aed"] then the smallest substring of N
18+
// that contains the characters a, e, and d is "dae" located at the end of the string.
19+
// So for this example your program should return the string dae.
20+
21+
// Another example: if strArr is ["aabdccdbcacd", "aad"] then the smallest substring
22+
// of N that contains all of the characters in K is "aabd" which is located at the
23+
// beginning of the string. Both parameters will be strings ranging in length from
24+
// 1 to 50 characters and all of K's characters will exist somewhere in the string N.
25+
// Both strings will only contains lowercase alphabetic characters.
26+
27+
// Examples
28+
// Input: {"ahffaksfajeeubsne", "jefaa"}
29+
// Output: aksfaje
30+
31+
// Input: {"aaffhkksemckelloe", "fhea"}
32+
// Output: affhkkse
33+
34+
public string MinWindowSubstring(string[] strArr, int arrLength)
35+
{
36+
string result = string.Empty;
37+
38+
string text = strArr[0];
39+
string pattern = strArr[1];
40+
41+
Dictionary<char, int> countMap = CreateCountMap(pattern);
42+
List<string> windows = extractWindows(text, pattern.Length);
43+
44+
foreach (string window in windows)
45+
{
46+
if (IsValidWindow(window, countMap))
47+
{
48+
if (String.IsNullOrEmpty(result))
49+
{
50+
result = window;
51+
}
52+
else if (window.Length < result.Length)
53+
{
54+
result = window;
55+
}
56+
}
57+
}
58+
59+
return result;
60+
}
61+
62+
protected Dictionary<char, int> CreateCountMap(string str)
63+
{
64+
Dictionary<char, int> countMap = new Dictionary<char, int>();
65+
66+
foreach (char c in str)
67+
{
68+
if (countMap.ContainsKey(c))
69+
{
70+
countMap[c]++;
71+
}
72+
73+
else
74+
{
75+
countMap.Add(c, 1);
76+
}
77+
}
78+
return countMap;
79+
}
80+
81+
protected List<string> extractWindows(string str, int length)
82+
{
83+
List<string> windows = new List<string>();
84+
int strLength = str.Length;
85+
86+
87+
for (int start = 0; start < strLength; start++)
88+
{
89+
for (int end = start + length; end < strLength + 1; end++)
90+
{
91+
windows.Add(str.Substring(start, end - start));
92+
}
93+
}
94+
95+
return windows;
96+
}
97+
98+
protected bool IsValidWindow(string window, Dictionary<char, int> patternMap)
99+
{
100+
bool isValid = true;
101+
102+
Dictionary<char, int> windowMap = CreateCountMap(window);
103+
104+
foreach(var item in patternMap)
105+
{
106+
var key = item.Key;
107+
var val = item.Value;
108+
109+
if (!windowMap.ContainsKey(key) || windowMap[key] < val)
110+
{
111+
isValid = false;
112+
}
113+
}
114+
115+
return isValid;
116+
}
117+
}
118+
}

‎Coderbyte_CSharp/Program.cs

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -28,6 +28,7 @@ static void Main(string[] args)
2828
tc.Test_KUniqueCharacters();
2929
tc.Test_NumberEncoding();
3030
tc.Test_PrimeMover();
31+
tc.Test_MinWindowSubstring();
3132
}
3233
}
3334
}

‎Coderbyte_CSharp/TestChallenge.cs

Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -200,6 +200,32 @@ public void Test_PrimeMover()
200200
Console.WriteLine("Output: {0}", prime.PrimeMover(num));
201201
Console.WriteLine();
202202
}
203+
204+
public void Test_MinWindowSubstring()
205+
{
206+
StringMinimumWindow minFinder = new StringMinimumWindow();
207+
208+
string text = "ahffaksfajeeubsne";
209+
string pattern = "jefaa";
210+
211+
string[] strArr = new string[2]{ text, pattern };
212+
213+
Console.WriteLine("Minimum Window Substring:");
214+
215+
Console.WriteLine("Input: {0} {1}", text, pattern);
216+
Console.WriteLine("Output: {0}", minFinder.MinWindowSubstring(strArr, strArr.Length));
217+
Console.WriteLine();
218+
219+
text = "aaffhkksemckelloe";
220+
pattern = "fhea";
221+
strArr[0] = text;
222+
strArr[1] = pattern;
223+
224+
Console.WriteLine("Input: {0} {1}", text, pattern);
225+
Console.WriteLine("Output: {0}", minFinder.MinWindowSubstring(strArr, strArr.Length));
226+
Console.WriteLine();
227+
228+
}
203229
#endregion
204230

205231
}

0 commit comments

Comments
 (0)