brenna.duffitt
BAN USERSolution in C++11
#include <iostream>
#include <string>
#include <set>
using namespace std;
int uniqueCharactersInString(const string& s)
{
set<char> unique;
for (const char& c : s)
if (unique.find(c) == unique.end())
unique.insert(c);
return unique.size();
}
string kLongestDistinctSubstring(const string& s, const int& k)
{
int follow = 0, //begining of the substring currently being evaluated
lead = k, //end of the substring currently being evaluated
beginIndex = 0, //instead of repeatedly storing the substring, we'll keep track of the indexes that it falls in
endIndex = k;
for (int i = 0; i <= s.length(); i++)
{
int tempLength = lead - follow;
if (uniqueCharactersInString(s.substr(follow, tempLength)) <= k)
{
if (tempLength > endIndex - beginIndex)
{
beginIndex = follow;
endIndex = lead;
}
lead++;
}
else
follow++;
}
return s.substr(beginIndex, endIndex - beginIndex);
}
int main(void)
{
string s;
int k;
cout << "String: ";
cin >> s;
cout << "Number of Unique characters: ";
cin >> k;
cout << kLongestDistinctSubstring(s, k) << endl;
system("Pause");
return 0;
}
My O(n) solution in C++14
- brenna.duffitt February 21, 2017