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