Substring Problems

Longest Substring

Sliding window algorithm

At Most Two Distinct Characters

Same as Fruit Into Baskets

1
2
3
4
5
1,2,3,2,2,4
^
{2,3,2,2}
^ ^
a b(2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int lengthOfLongestSubstringTwoDistinct(string s) {
int res = 0, curr = 0, last = 0;
int a = -1, b = -1;
for (int c : s) {
curr = (c == a || c == b) ? curr+1 : last+1;

if (c == b) {
last++;
} else {
last = 1;
a = b; b = c;
}

res = max(res, curr);
}

return res;
}

Decode

Valid Email

1
2
3
4
5
6
7
8
9
10
11
12
13
string valid_email(const string& email)
{
string res;
auto it_at = find(email.begin(), email.end(), '@');
auto it_plus = find(email.begin(), it_at, '+');
for (auto k = email.begin(); k < it_plus; k++)
{
if (*k != '.') res.push_back(*k);
}
copy(it_at, email.end(), back_inserter(res));

return res;
}