# Clean 11 lines AC answer, O(1) space, O(n) time.

• I submitted this solution two months ago and I can't even remember whether I wrote myself or copied from others. I don't understand it now but find it AC and much shorter than other posts here.

``````int lengthOfLongestSubstringTwoDistinct(string s) {
int i = 0, j = -1;
int maxLen = 0;
for (int k = 1; k < s.size(); k++) {
if (s[k] == s[k-1]) continue;
if (j > -1 && s[k] != s[j]) {
maxLen = max(maxLen, k - i);
i = j + 1;
}
j = k - 1;
}
return maxLen > (s.size() - i) ? maxLen : s.size() - i;
}``````

• smart idea.I think it uses i and j to track the last indices of two characters. i is tracking the first character, j is tracking the second character. But I still like the hashmap solution because we can easily extend that solution to K distinct characters.

• good comment!

• A little bit not like tracking both two indices.
I think here i is recording the first occurrence position of the new result.

• @blayer After analysis and reproducing the solution, I see that i and j do not tracking the first and second characters. My analysis is as follows:

The 2-unique-character substrings can be thought of consisting of blocks of unique characters (denote a for a first character and b for a second character in the following graph).

`````` | a    |   b   |   a |    b    |
+------+-------+-----+---------+
``````

i marks the first occurrence of the 2-unique-character substring
j marks the last occurrence of 2nd block since k
k marks the currently considered character
if s[k] != s[k-1] --> s[k] is different from the previous block
--> always mark j = k - 1
and if s[k] != s[j] --> s[k] is also different from the previous previous block
--> so we have a 3rd character at k

• @blayer not exactly, i marks the start of current tracking, and j marks the one's different neighbor.

• A good solution beating more than 80%! I reimplemented it using Java:

""""
public int lengthOfLongestSubstringTwoDistinct(String str) {
int i = 0, j = -1;
int maxLen = 0;
char[] s = str.toCharArray();
for (int k = 1; k < s.length; k++) {
if (s[k] == s[k-1]) continue;
if (j > -1 && s[k] != s[j]) {
maxLen = Math.max(maxLen, k - i);
i = j + 1;
}
j = k - 1;
}
return maxLen > (s.length - i) ? maxLen : s.length - i;
}
""""

• This is so clever. Do you remember how did you come up with this solution?

• This is really a good answer. Much cleaner than using flags. Here are my comments for others:

``````public:
int lengthOfLongestSubstringTwoDistinct(string s) {
// xy....x yyyyy z
// xy....y xxxxx z
// i     j       k
// i start of the 2-char substring
// j the last position other than the last char in the substring
// k current position to check
// e.g. let's say current substring is as above.
// Now we find a new char 'z' at position k. We can only keep s[k-1] and s[k] for the new substring.
// So we need to scan from the tail until we hit a char other than s[k-1] at position j.
// And we need to abandon all chars <= j.
// Also, we could imagine there is always a new char after the end of string.
// So we need to do an extra check s.size() - i.
const int N = s.size();
int i = 0, j = -1, max_len = 0;
for (int k = 1; k < N; ++k) {
if (s[k] == s[k-1]) continue;
if (j > -1 && s[k] != s[j]) {
max_len = max(max_len, k - i);
i = j + 1;
}
j = k - 1;
}
return max(max_len, (int)s.size() - i);
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.