solved 'Minimum Window Substring' on leetcode https://leetcode.com/problems/minimum-window-substring/

min_window_substr.c

/** 
 * Algorithm inspired from 
 * https://leetcode.com/discuss/44100/16ms-simple-solution-only-using-vector-detailed-explanation
 **/ 

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char* minWindow(char* s, char* t) {
  // Counts of chars in t to match,
  // all are ascii so use 128-element array.
  int remain_char_counts[128] = { 0 };
  int chars_to_match = 0;
  // Set up chars to collect.
  for (int i = 0; t[i] != '\0'; ++i) {
    ++remain_char_counts[t[i]];
    ++chars_to_match;
  }
  
  // Record the left, right index as the final answer.
  int left = 0, right = ~(1 << 31);
  // Two pointers to specify the window.
  int start = 0, end = 0;
  while (1) {
    if (chars_to_match != 0) {
      // Current window not matching t.
      
      // Break if reaching end of s.
      if (!s[end]) {
        break;
      }
      // Advance `end`.
      --remain_char_counts[s[end]];
      if (remain_char_counts[s[end]] >= 0) {
        // Processed is a char of t.
        --chars_to_match;
      }
      ++end;
    } else {
      // Current window matches t. But defer answer
      // recording only if s[start] is a char of t.
      ++remain_char_counts[s[start]];
      if (remain_char_counts[s[start]] > 0) {
        // This is a char of t.
        ++chars_to_match;
        // Window matched, record the pos. Put this part
        // inside if is a minor optimization.
        if (end - start < right - left) {
          left = start;
          right = end;
        }
      }
      ++start;
    }
  }
  if (right == ~(1 << 31)) {
    // No matching window found. Let res = "".
    right = left;
  }
  
  char *res = (char *) malloc(sizeof(char) * (right - left + 1));
  strncpy(res, s + left, right - left);
  res[right - left] = '\0';
  return res;
}

int main() {
  char *res;
  
  res = minWindow("ADOBECODEBANC", "ABC");
  assert(!strcmp(res, "BANC"));
  free(res);
  
  res = minWindow("ab", "a");
  assert(!strcmp(res, "a"));
  free(res);
  
  res = minWindow("ab", "c");
  assert(!strcmp(res, ""));
  free(res);  
  
  res = minWindow("abfas", "abfas");
  assert(!strcmp(res, "abfas"));
  free(res);  

  res = minWindow("", "adsfadf");
  assert(!strcmp(res, ""));
  free(res);
  
  res = minWindow("adsfadf", "");
  assert(!strcmp(res, ""));
  free(res);  
  
  res = minWindow("", "");
  assert(!strcmp(res, ""));
  free(res);  

  return 0;
}

min_window_substr.cc

#include <cassert>
#include <iostream>

using namespace std;

// Similar to following two gists:
// https://gist.github.com/EDFward/7869ecfdf04ae607d160#file-subarray_sum-cc
// https://gist.github.com/EDFward/b4b71ace86101f70cde6#file-duplicate_iii-cc
class Solution {
  public:
    string minWindow(string s, string t) {
      int remains[128] = { 0 };
      // Number of chars to match.
      int required_match = t.size();
      for (char ch : t) {
        ++remains[ch];
      }

      int start = 0;
      int min_left = 0, min_len = INT_MAX;
      for (int i = 0, len = s.size(); i < len; ++i) {
        --remains[s[i]];
        // >= 0 means this is a required char to match.
        if (remains[s[i]] >= 0) {
          --required_match;
        }
        while (required_match == 0) {
          // Record the start and length.
          if (i - start < min_len) {
            min_len = i - start;
            min_left = start;
          }

          ++remains[s[start]];
          // Check if `s[start]` is a required char.
          if (remains[s[start]] > 0) {
            ++required_match;
          }
          ++start;
        }
      }
      return min_len == INT_MAX ? "" : s.substr(min_left, min_len + 1);
    }
};

int main(int argc, char *argv[]) {
  Solution sol;
  string res;
  
  res = sol.minWindow("ADOBECODEBANC", "ABC");
  assert(res == "BANC");
  
  res = sol.minWindow("ab", "a");
  assert(res == "a");
  
  res = sol.minWindow("ab", "c");
  assert(res == "");
  
  res = sol.minWindow("abfas", "abfas");
  assert(res == "abfas");
  
  res = sol.minWindow("", "adgdsa");
  assert(res == "");
  
  res = sol.minWindow("", "");
  assert(res == "");
}