Created
February 18, 2018 19:10
-
-
Save jianminchen/c6060ecac7d0fddfc97bf89cd688ada5 to your computer and use it in GitHub Desktop.
Find minimum substring - Feb. 18, 2018 - code review the peer's performance
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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