Skip to content

Instantly share code, notes, and snippets.

Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jianminchen/c26228a3f785be8331fed3f79aa63638 to your computer and use it in GitHub Desktop.
Save jianminchen/c26228a3f785be8331fed3f79aa63638 to your computer and use it in GitHub Desktop.
Leetcode 76 Minimum windows substring - write C# code based on one of discussion, pass Leetcode online judge
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Leetcode76_minimum_window_substring
{
/// <summary>
/// Leetcode 76: Minimum window substring
/// </summary>
class Program
{
static void Main(string[] args)
{
}
/// <summary>
/// code review - Julia works on the code on April 3, 2018
/// </summary>
/// <param name="source"></param>
/// <param name="pattern"></param>
/// <returns></returns>
public String minWindow(String source, String pattern) {
var map = new int[256];
foreach(char c in pattern.ToCharArray()){
map[c - 'A']++;
}
int minLen = int.MaxValue;
int minStart = 0;
var totalNeedFound = pattern.Length;
var sourceCharArray = source.ToCharArray();
int start = 0;
int end = 0;
while(end < sourceCharArray.Length){
int endChar = sourceCharArray[end] - 'A';
map[endChar]--;
if(map[endChar] >= 0){ // still need more endChar
totalNeedFound--;
}
if(totalNeedFound == 0){
int startChar = sourceCharArray[start] - 'A';
while(map[startChar] < 0){ // extra char is found
map[startChar]++;
start++;
startChar = sourceCharArray[start] - 'A';
}
int currentLength = end - start + 1;
if(currentLength < minLen){
minLen = currentLength;
minStart = start;
}
map[startChar]++;
start++;
totalNeedFound++;
}
end++;
}
return minLen == int.MaxValue ? "" : source.Substring(minStart, minLen);
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment