Longest Substring At most k

Given a string, find the length of the longest substring T that contains at most 2 distinct characters.

  • Time: O(n)
  • Space: O(1)
public int lengthOfLongestSubstringAtMost(String s) {
    int[] count = new int[256];
    int distinct = 0, maxLen = 0, j = 0;
    for (int i = 0; i < s.length(); i++) {
        if (count[s.charAt(i)] == 0)
            distinct++;
        count[s.charAt(i)]++;
        while (distinct > 2) {
            count[s.charAt(j)]--;
            if (count[s.charAt(j)] == 0) {
                distinct--;
            }
            j++;
        }
        maxLen = Math.max(i - j + 1, maxLen);
    }
    return maxLen;
}

results matching ""

    No results matching ""