Skip to content

Instantly share code, notes, and snippets.

@jianminchen
Created February 18, 2018 19:10
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/c6060ecac7d0fddfc97bf89cd688ada5 to your computer and use it in GitHub Desktop.
Save jianminchen/c6060ecac7d0fddfc97bf89cd688ada5 to your computer and use it in GitHub Desktop.
Find minimum substring - Feb. 18, 2018 - code review the peer's performance
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <unordered_map>
#include <limits>
using namespace std;
/*
0 0 0
x,y,z = 2
substr = start ,end
count
01234567
xaxyyzyzyx -> xaxyyz -> "xyyz"
s e
*/
//bool allcharsfound(vector<char>& arr, char added, unordered_map<char, int> &map, int &count){
/* if(map.find(added)!=map.end())
map[added]++;
else{
map[added]=1;
count--;
}
retrun(count ==0)
*/
//}
string getShortestUniqueSubstring( const vector<char>& arr, const string &str )
{
int count = arr.size();
int left = 0;
int right = 0;
int sub_start = 0 , sub_end = 0;
int sub_string_len = INT_MAX;
unordered_map<char,int> map; // x, y, z 1, 1, 1 -> 0, no -1, extra x, extra y - smart pointer 0, add to 1, count-
for(int i = 0 ; i< arr.size();i++)
map[arr[i]] = 0;
while(left <= right && right < str.length()){
//if(allcharsfound(arr, str[right++],map,count)
if(map.find(str[right]) != map.end()){
map[str[right]]++;
if( map[str[right]] == 1)
{
count--;
}
}
else
{
right++;
continue; // skip D it is not in unique chars -> minimum substring xyzaaa, "xyz" -> yza
}
while(count == 0){ // found a window with all chars xaxxxyz -> skip 3 'x', x, a, x, x, min , x -> line 34
if(sub_string_len > right + 1 - left){
//update ou
sub_start = left;
sub_end = right;
sub_string_len = right - left + 1;
}
//update count to move left
if(map.find(str[left])!=map.end()) {
map[str[left]]--;
if(map[str[left]] == 0 )
count++;
}
left++;
}
right++;
}//have not reached the end of the str
return sub_string_len == INT_MAX ? "" : (str.substr(sub_start,sub_end - sub_start + 1)); // index, length
}
int main() {
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment