LeetCode 159.Longest Substring with At Most Two Distinct Characters--Java,C++,Python解法

LeetCode問題解コラム:LeetCode問題解LeetCodeすべての問題まとめ:LeetCodeすべての問題まとめ大部分の問題C+,Python,Javaの解法があります.
タイトルアドレス:Longest Substring with At Most Two Distinct Characters-LeetCode
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の難易度で、問題の意味は簡単で、最大2つの異なる文字を持つ最長男列の長さを見つけることです.
問題を見るとO(n)の時間の複雑さがこの問題を作ることができるはずだと感じます.
20分ほどコードを書いた後、Python解法が出てきました.

class Solution:
    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:
        count = 0
        p = {
     }
        l = {
     }
        for now in range(0, len(s)):
            i = s[now]
            p[i] = now
            if len(l) < 2 and i not in l:
                l[i] = 1
            elif i in l:
                l[i] += 1
            else:
                if count < sum(l.values()):
                    count = sum(l.values())
                for j in l.keys():
                    if j != s[now-1]:
                        l.pop(j)
                        l[list(l.keys())[0]] = now-p[j]-1
                        break
                l[i] = 1
        if l != {
     }:
            if count < sum(l.values()):
                count = sum(l.values())
        return count

私の解法は少し面倒ですが、分かりやすくて、一番速い解法は以下の通りです.

class Solution:
    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:
        i, l, k = -1, 0, 0
        for j in range(1, len(s)):
            if s[j] != s[j-1]:
                if i > -1 and s[i] != s[j]:
                    l, k = i+1, max(k, j-l)
                i = j-1
        return max(k, len(s)-l)

核心的な考え方は私のやり方と同じです.
違いは、iとjを使用して2文字の最後のインデックスを追跡することです.i最初の文字を追跡し、jは2番目の文字を追跡する.しかし、私はhashmapソリューションが好きです.私たちはこのソリューションをK個の異なる文字に簡単に拡張することができるからです.
C++解法は以下の通りである.

class Solution
{
     
public:
    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;
    }
};

他の人のJavaの解法は以下の通りです.

class Solution {
     
    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;
    }
}