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


  • 25
    E

    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;
        }

  • 13
    B

    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.


  • 0
    K

    good comment!


  • 0
    T

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


  • 2
    D

    @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


  • 1

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


  • 0
    N

    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;
    }
    """"


  • 0
    X

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


  • 2
    B

    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);
        }
    };
    

Log in to reply
 

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