shortest substring containing all letters in a set of letters

shortestSubstringContainingChars_dynProg.cpp

#include <iostream>
#include <vector>
#include <string>

using namespace std;

vector<bool> GetArrMap(const vector<char> &arr) {
  vector<bool> arrMap(256, false);

  for (char curChar : arr) arrMap[curChar] = true;

  return arrMap;

}

string::const_iterator RegisterChar(string::const_iterator lastChar, const vector<bool> &arrMap, string::const_iterator addedChar, vector<int> &matchMap, int &matched) {

  if (addedChar != lastChar && arrMap[*addedChar] && matchMap[*addedChar]++ == 0) matched++;

  return addedChar;

}

void UnregisterChar(const vector<bool> &arrMap, string::const_iterator &removedChar, vector<int> &matchMap, int &matched) {

  if (arrMap[*removedChar] && --(matchMap[*removedChar]) == 0) matched--;

  removedChar++;

}

string getShortestUniqueSubstring( const vector<char>& arr, const string &str )
{
  const vector<bool> arrMap = GetArrMap(arr);
  string::const_iterator startChar = str.cbegin();
  string::const_iterator shortestStart = startChar;
  int shortestLen = 0;
  int matched = 0;
  vector<int> matchMap(256, 0);

  if (arr.empty()) return "";

  for (string::const_iterator endChar = RegisterChar(str.cend(), arrMap, startChar, matchMap, matched); endChar != str.cend(); RegisterChar(str.cend(), arrMap, ++endChar, matchMap, matched)) {

    for (; matched == arr.size(); UnregisterChar(arrMap, startChar, matchMap, matched)) {

      shortestStart = startChar;
      shortestLen = endChar - startChar + 1;

    }

    if (shortestLen == arr.size()) return string(shortestStart, shortestStart + shortestLen);

    if (shortestLen > 0) UnregisterChar(arrMap, startChar, matchMap, matched);

  }

  return string(shortestStart, shortestStart + shortestLen);

}

int main() {
  return 0;
}

shortestSubstringContainingChars_n+l.cpp

#include <iostream>
#include <vector>
#include <string>

using namespace std;

vector<bool> GetArrMap(const vector<char> &arr) {
  vector<bool> arrMap(256, false);

  for (char curChar : arr) arrMap[curChar] = true;

  return arrMap;

}

vector<int> GetRelevantIndices(const string &str, const vector<bool> &arrMap) {
  vector<int> indices;

  indices.reserve(str.size());

  for (int idx = 0; idx < str.size(); idx++) if (arrMap[str[idx]]) indices.push_back(idx);

  return indices;

}

void RegisterChar(char addedChar, vector<int> &matchMap, int &matched) {

  if (matchMap[addedChar]++ == 0) matched++;

}

void UnregisterChar(char removedChar, vector<int> &matchMap, int &matched) {

  if (--(matchMap[removedChar]) == 0) matched--;

}

string getShortestUniqueSubstring( const vector<char>& arr, const string &str )
{
  const vector<bool> arrMap = GetArrMap(arr);
  const vector<int> relevantIndices = GetRelevantIndices(str, arrMap);
  vector<int>::const_iterator startIdx = relevantIndices.cbegin();
  vector<int>::const_iterator endIdx = startIdx;
  int shortestStart = 0;
  int shortestLen = 0;
  int matched = 0;
  vector<int> matchMap(256, 0);

  if (arr.empty() || relevantIndices.empty()) return "";

  RegisterChar(str[*endIdx], matchMap, matched);

  while (endIdx != relevantIndices.cend()) if (matched == arr.size()) {

    shortestStart = *startIdx;
    shortestLen = *endIdx - *startIdx + 1;

    if (shortestLen == matched) return str.substr(shortestStart, shortestLen);

    UnregisterChar(str[*(startIdx++)], matchMap, matched);

  } else if (++endIdx != relevantIndices.cend()) {

    RegisterChar(str[*endIdx], matchMap, matched);

    if (shortestLen > 0) for (; *endIdx - *startIdx + 1 >= shortestLen; startIdx++) UnregisterChar(str[*startIdx], matchMap, matched);

  }

  return str.substr(shortestStart, shortestLen);

}

int main() {
  return 0;
}

shortestSubstringContainingChars_nPow2+l.cpp

#include <iostream>
#include <vector>
#include <string>

using namespace std;

vector<bool> GetArrMap(const vector<char> &arr) {
  vector<bool> arrMap(256, false);

  for (char curChar : arr) arrMap[curChar] = true;

  return arrMap;

}

string GetShortestMatch(const vector<bool> &arrMap, int targetSize, const string &str, int startIdx) {
  int matched = 0;
  vector<bool> matchMap(256, false);

  for (int endIdx = startIdx; endIdx < str.size(); endIdx++) if (arrMap[str[endIdx]]) if (!matchMap[str[endIdx]]) {

    matchMap[str[endIdx]] = true;
    matched++;

    if (matched == targetSize) return str.substr(startIdx, endIdx - startIdx + 1);

  }

  return "";

}

string getShortestUniqueSubstring( const vector<char>& arr, const string &str )
{
  const vector<bool> arrMap = GetArrMap(arr);
  string shortestMatch = "";

  for (int count = 0; count <= str.size() - arr.size(); count++) {

    string match = GetShortestMatch(arrMap, arr.size(), str, count);

    if (match.size() == arr.size()) return match;

    if (match.empty()) return shortestMatch;

    if (shortestMatch.empty() || match.size() < shortestMatch.size()) shortestMatch = match;

  }

}

int main() {
  return 0;
}