I am trying to find the longest substring with at most 2 distinct characters. It is a brute force program which just uses all possible substrings and checks if they have 2 or more distinct chars.

I use a set to keep track of the distinct chars.

```
#include <iostream>
#include <string>
#include <algorithm>
#include <unordered_set>
using namespace std;
int main()
{
string s = "AllPossibleSubstrings";
int l=0,index=0;
for(int i =0;i<s.length();i++)
{
for(int j=i+1;j<s.length();j++)
{
string sub = string(s.begin()+i,s.begin()+j);
unordered_set<char> v;
for(auto x:sub)
{
v.insert(x);
}
if(v.size()<=2) {l=max(l,j-i+1); if(l==j-i+1) index=i;}
}
}
cout<<l<<" "+s.substr(index,l)<<endl;
}
```

I get the wrong answer of `4 ssib`

, while the correct answer must not have b (All, llP, oss, ssi are possible answers). Where am I doing wrong ?

# Best How To :

If you add debug output to your code to see which strings does it find:

```
if(v.size()<=2) {
l=max(l,j-i+1);
if(l==j-i+1) {
index=i;
cout << "Found match " << i << " " << j << " " << l << " " << sub << endl;
}
}
```

you'll see that it finds the proper strings:

```
Found match 0 1 2 A
Found match 0 2 3 Al
Found match 0 3 4 All
Found match 1 4 4 llP
Found match 4 7 4 oss
Found match 5 8 4 ssi
```

(see here: http://ideone.com/lQqgnq)

But you will also see that, for example, for `i=5`

and `j=8`

you get `sub="ssi"`

, but `l=4`

, which is clearly wrong.

So the reason for wrong behavior is that `string(s.begin()+i,s.begin()+j)`

makes the substring starting from `i`

-th character and upto, *but not including*, the `j`

-th character: http://www.cplusplus.com/reference/string/string/string/ :

```
template <class InputIterator>
string (InputIterator first, InputIterator last);
```

Copies the sequence of characters in the range [first,last), in the same order.

Note that `last`

is not included.

So your `l`

should be calculated correspondingly: as `j-i`

, not `j-i+1`

.

In fact, the reason is that your code is overcomplicated. You clearly use `s.substr`

at the end of your code, why do not you use the same in the main loop? You could even have looped over `i`

and `l`

, and then you would not have such problems.

Moreover, in fact you do not need to extract a substring each time. You can loop over `i`

and `l`

and just keep currect set of different chars. This will yield a faster `O(N^2)`

solution, while yours is `O(N^3)`

. Something like:

```
for (int i=0; i<s.length(); i++) {
unordered_set<char> v;
for (int l=1; l<s.length()-i; l++)
v.insert(s[i+l-1]);
if (v.size()>2) break;
if (l>maxl) {
index = i;
maxl = l;
}
}
```

In fact, even an `O(N)`

solution can also be achieved here, but with a bit more advanced code.