Leetcode 159 Longest Substring with At Most Two Distinct Characters G家OA原题

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

Example 1:

Input: "eceba"
Output: 3
Explanation: t is "ece" which its length is 3.

Example 2:

Input: "ccaabbb"
Output: 5
Explanation: t is "aabbb" which its length is 5.

题意分析

尽管这是一道hard级别的Google OA原题，但是难度却不是很大。这道题的基本想法是通过[begin,end]维护一个从左到右扫描的移动窗口，这是一个很常规的想法。假设源字符串长度为m，窗口长度为n,根据我们对sliding window, 一般有两种复杂度
1. 基础复杂度： O(mn) 即移动过程中对窗口内数据进行遍历
2. 优化复杂度： O(m) 即移动过程中不对窗口内数据遍历，而是只做常数级别的操作
本题由于给定2 distinct characters，因此优化复杂度的做法是很平凡的

代码

采用移动窗口，每次end向后移动一位，每次移动中严格只存在常数次的操作。

class Solution {
    public int lengthOfLongestSubstringTwoDistinct(String s) {
        char[] chars = new char[2];
        int[]  locs  = new int[2];
        int begin=0,end=0,max_length = -1,count = 0;
        while (end<s.length()){
            char ch = s.charAt(end);
            if (ch!=chars[0] && ch!=chars[1] && count<2){
                chars[count] = ch;
                locs[count]  = end;
                count++;
            } else if (ch==chars[1]){
                locs[1] = end;
            } else if (ch==chars[0]) {
                locs[0] = end;
            } else if (ch!=chars[0] && ch!=chars[1]){
                int oldNo = locs[1]>locs[0]?0:1;
                chars[oldNo] = ch;
                begin = locs[oldNo]+1;
                locs[oldNo] = end;
            }
            max_length = end-begin+1>max_length ? end-begin+1 : max_length;
            end++;
        }
        return max_length;
    }
}