malpanimridul
BAN USERThe Following fully working code. Time Complexity - O(n*lg n) .
#include<string>
#include<set>
#include<iostream>
#include<map>
using namespace std;
string minLength(const set<char> &s, const string word)
{
int low = s.size(), high = word.size()-1, mid;
map<char,int> counting_map;
int count;
while(low < high)
{
mid = low + (high-low)/2;
bool flag = false;
count = 0;
counting_map.clear();
/*code to check whether we can have a string of len mid
* which contains all characters of the set.
*/
for(int i=0; i<mid; i++)
{
counting_map[word[i]]++;
// To count one char once only.
if(counting_map[word[i]] == 1)
count++;
}
if(count == s.size())
flag = true;
else
{
for(int i= mid; i<word.size(); i++)
{
counting_map[word[i-mid]]--;
if(counting_map[word[i-mid]] == 0)
count--;
counting_map[word[i]]++;
// To count one char once only.
if(counting_map[word[i]] == 1)
count++;
if(count == s.size())
{
flag = true;
break;
}
}
}
if(flag)
{
high = mid;
}
else
{
low = mid+1;
}
}
/*low is the length of the substring with the given properties*/
count = 0;
counting_map.clear();
cout << "min lengthh is - " << low <<endl;
for(int i=0; i<low; i++)
{
counting_map[word[i]]++;
// To count one char once only.
if(counting_map[word[i]] == 1)
count++;
}
cout <<"count-1: " <<count ;
if(count == s.size())
return word.substr(0, low);
for(int i= low; i<word.size(); i++)
{
counting_map[word[i-low]]--;
if(counting_map[word[i-low]] == 0)
count--;
cout <<"count-2: " <<count ;
counting_map[word[i]]++;
// To count one char once only.
if(counting_map[word[i]] == 1)
count++;
cout <<"count-3: " <<count ;
if(count == s.size())
return word.substr(i-low+1, low);
}
return "?";
}
int main()
{
set<char> s;
s.insert('a');
s.insert('b');
s.insert('c');
string word = "baacaab";
cout << "min_length_substring.cpp\n";
cout << "\n Substring (Ans) = " << minLength(s,word);
return 0;
}
- malpanimridul February 11, 2015