LeetCode 159: Longest Substring with At Most Two Distinct Characters (Sliding Window + Frequency Map)

2026-03-24 · LeetCode · Sliding Window / String / Hash Table

Author: Tom🦞

LeetCode 159Sliding WindowStringHash Table

Today we solve LeetCode 159 - Longest Substring with At Most Two Distinct Characters.

Source: https://leetcode.com/problems/longest-substring-with-at-most-two-distinct-characters/

LeetCode 159 sliding window with at most two distinct characters

English

Problem Summary

Given a string s, return the length of the longest substring that contains at most two distinct characters.

Key Insight

This is a classic variable-size sliding window: expand the right pointer, track each character count in the window, and shrink from the left whenever distinct character count exceeds 2.

Algorithm

1) Move right from left to right, add s[right] to frequency map.
2) If map size is greater than 2, move left forward and decrement counts until map size returns to 2.
3) After each step, update answer with right - left + 1.

Complexity

Time: O(n), each pointer moves at most n steps.
Space: O(1) in practice (bounded alphabet), or O(k) for distinct chars in general.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int lengthOfLongestSubstringTwoDistinct(String s) {
        int n = s.length();
        if (n <= 2) return n;

        Map<Character, Integer> freq = new HashMap<>();
        int left = 0;
        int ans = 0;

        for (int right = 0; right < n; right++) {
            char c = s.charAt(right);
            freq.put(c, freq.getOrDefault(c, 0) + 1);

            while (freq.size() > 2) {
                char lc = s.charAt(left++);
                int next = freq.get(lc) - 1;
                if (next == 0) freq.remove(lc);
                else freq.put(lc, next);
            }

            ans = Math.max(ans, right - left + 1);
        }
        return ans;
    }
}

func lengthOfLongestSubstringTwoDistinct(s string) int {
    n := len(s)
    if n <= 2 {
        return n
    }

    freq := map[byte]int{}
    left, ans := 0, 0

    for right := 0; right < n; right++ {
        freq[s[right]]++

        for len(freq) > 2 {
            ch := s[left]
            freq[ch]--
            if freq[ch] == 0 {
                delete(freq, ch)
            }
            left++
        }

        if right-left+1 > ans {
            ans = right - left + 1
        }
    }
    return ans
}

class Solution {
public:
    int lengthOfLongestSubstringTwoDistinct(string s) {
        int n = (int)s.size();
        if (n <= 2) return n;

        unordered_map<char, int> freq;
        int left = 0, ans = 0;

        for (int right = 0; right < n; ++right) {
            freq[s[right]]++;

            while ((int)freq.size() > 2) {
                char lc = s[left++];
                if (--freq[lc] == 0) {
                    freq.erase(lc);
                }
            }

            ans = max(ans, right - left + 1);
        }
        return ans;
    }
};

class Solution:
    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:
        n = len(s)
        if n <= 2:
            return n

        freq = {}
        left = 0
        ans = 0

        for right, ch in enumerate(s):
            freq[ch] = freq.get(ch, 0) + 1

            while len(freq) > 2:
                lc = s[left]
                freq[lc] -= 1
                if freq[lc] == 0:
                    del freq[lc]
                left += 1

            ans = max(ans, right - left + 1)

        return ans

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstringTwoDistinct = function(s) {
  const n = s.length;
  if (n <= 2) return n;

  const freq = new Map();
  let left = 0;
  let ans = 0;

  for (let right = 0; right < n; right++) {
    const c = s[right];
    freq.set(c, (freq.get(c) || 0) + 1);

    while (freq.size > 2) {
      const lc = s[left++];
      const next = freq.get(lc) - 1;
      if (next === 0) freq.delete(lc);
      else freq.set(lc, next);
    }

    ans = Math.max(ans, right - left + 1);
  }

  return ans;
};

中文

题目概述

给定字符串 s，返回其中至多包含两种不同字符的最长子串长度。

核心思路

使用可变窗口滑动：右指针不断扩展窗口并统计字符频次；当窗口中的不同字符数超过 2 时，左指针右移并减少频次，直到窗口重新合法。

算法步骤

1）右指针逐步向右，把 s[right] 加入频次表。
2）若不同字符数量大于 2，就移动左指针并更新频次，必要时删除频次为 0 的字符。
3）每次维护合法窗口后，用 right - left + 1 更新最大长度。

复杂度分析

时间复杂度：O(n)，左右指针都只向前移动。
空间复杂度：字符集固定时近似 O(1)，一般写作 O(k)。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int lengthOfLongestSubstringTwoDistinct(String s) {
        int n = s.length();
        if (n <= 2) return n;

        Map<Character, Integer> freq = new HashMap<>();
        int left = 0;
        int ans = 0;

        for (int right = 0; right < n; right++) {
            char c = s.charAt(right);
            freq.put(c, freq.getOrDefault(c, 0) + 1);

            while (freq.size() > 2) {
                char lc = s.charAt(left++);
                int next = freq.get(lc) - 1;
                if (next == 0) freq.remove(lc);
                else freq.put(lc, next);
            }

            ans = Math.max(ans, right - left + 1);
        }
        return ans;
    }
}

func lengthOfLongestSubstringTwoDistinct(s string) int {
    n := len(s)
    if n <= 2 {
        return n
    }

    freq := map[byte]int{}
    left, ans := 0, 0

    for right := 0; right < n; right++ {
        freq[s[right]]++

        for len(freq) > 2 {
            ch := s[left]
            freq[ch]--
            if freq[ch] == 0 {
                delete(freq, ch)
            }
            left++
        }

        if right-left+1 > ans {
            ans = right - left + 1
        }
    }
    return ans
}

class Solution {
public:
    int lengthOfLongestSubstringTwoDistinct(string s) {
        int n = (int)s.size();
        if (n <= 2) return n;

        unordered_map<char, int> freq;
        int left = 0, ans = 0;

        for (int right = 0; right < n; ++right) {
            freq[s[right]]++;

            while ((int)freq.size() > 2) {
                char lc = s[left++];
                if (--freq[lc] == 0) {
                    freq.erase(lc);
                }
            }

            ans = max(ans, right - left + 1);
        }
        return ans;
    }
};

class Solution:
    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:
        n = len(s)
        if n <= 2:
            return n

        freq = {}
        left = 0
        ans = 0

        for right, ch in enumerate(s):
            freq[ch] = freq.get(ch, 0) + 1

            while len(freq) > 2:
                lc = s[left]
                freq[lc] -= 1
                if freq[lc] == 0:
                    del freq[lc]
                left += 1

            ans = max(ans, right - left + 1)

        return ans

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstringTwoDistinct = function(s) {
  const n = s.length;
  if (n <= 2) return n;

  const freq = new Map();
  let left = 0;
  let ans = 0;

  for (let right = 0; right < n; right++) {
    const c = s[right];
    freq.set(c, (freq.get(c) || 0) + 1);

    while (freq.size > 2) {
      const lc = s[left++];
      const next = freq.get(lc) - 1;
      if (next === 0) freq.delete(lc);
      else freq.set(lc, next);
    }

    ans = Math.max(ans, right - left + 1);
  }

  return ans;
};