✡ leetcode 159. Longest Substring with At Most Two Distinct Characters 求两个字母组成的最大子串长度 --------- java

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

For example, Given s = “eceba”,

T is "ece" which its length is 3.

给一个字符串，求这个字符串中，由两个字母组成的，连续的最长子串的长度。

虽然是hard，但是感觉并没有什么难度。

用ch1和preCh记录当前两个字母，preCh记录的是上一个字母(s.charAt(i-1))，same记录的是preCh这个字母重复出现的次数，这样出现第三个字母的时候，就可以直接得出从0到i由后两个字母组成的长度为same+1，并没有使用其他的数据结构。

时间O(n),空间O(1).

public class Solution {

    public int lengthOfLongestSubstringTwoDistinct(String s) {

        int len = s.length();

        if (len < 3){

            return len;

        }

        char ch1 = s.charAt(0);

        int same = 0;

        while (same < len && s.charAt(same) == ch1){

            same++;

        }

        if (same == len){

            return len;

        }

        char preCh = s.charAt(same);

        int result = same + 1;

        int ans = same + 1;

        int i = same + 1;

        same = 1;

        for (; i < len; i++){

            if (s.charAt(i) == preCh){

                result++;

                same++;

            } else if (s.charAt(i) == ch1){

                result++;

                same = 1;

                ch1 = preCh;

                preCh = s.charAt(i);

            } else {

                ch1 = preCh;

                preCh = s.charAt(i);

                ans = Math.max(ans, result);

                result = same + 1;

                same = 1;

            }

        }

        ans = Math.max(ans, result);

        return ans;

    }

}

2、还可以利用hashMap来做：（参考discuss）

　　Map数目小于3的时候将字母和他的位置加入Map中。

　　如果是大于等于3，那么找出距离位置hi最远的一个字母（leftMost），删掉，从leftMost的下一个字母开始到当前位置hi就是当前两个字母的长度。

public class Solution {

    public int lengthOfLongestSubstringTwoDistinct(String s) {

        if(s.length() < 1) return 0;

        HashMap<Character,Integer> index = new HashMap<Character,Integer>();

        int lo = 0;

        int hi = 0;

        int maxLength = 0;

        while(hi < s.length()) {

            if(index.size() <= 2) {

                char c = s.charAt(hi);

                index.put(c, hi);

                hi++;

            }

            if(index.size() > 2) {

                int leftMost = s.length();

                for(int i : index.values()) {

                    leftMost = Math.min(leftMost,i);

                }

                char c = s.charAt(leftMost);

                index.remove(c);

                lo = leftMost+1;

            }

            maxLength = Math.max(maxLength, hi-lo);

        }

        return maxLength;

    }

}

3、其实不算算法，就是把s先转换成char[]。这样就会达到最快。

public class Solution {

    public int lengthOfLongestSubstringTwoDistinct(String s) {

        int len = s.length();

        if (len < 3){

            return len;

        }

        char[] words = s.toCharArray();

        char ch1 = words[0];

        int i = 1;

        while (i < len && words[i] == ch1){

            i++;

        }

        if (i == len){

            return len;

        }

        int same = 1;

        char preCh = words[i];

        int ans = i + 1;

        int result = ans;

        i++;

        while (i < len){

            if (words[i] == preCh){

                result++;

                same++;

            } else if (words[i] == ch1){

                result++;

                same = 1;

                ch1 = preCh;

                preCh = words[i];

            } else {

                ch1 = preCh;

                preCh = words[i];

                ans = Math.max(ans, result);

                result = same + 1;

                same = 1;

            }

            i++;

        }

        ans = Math.max(ans, result);

        return ans;

    }

}

巴特西

✡ leetcode 159. Longest Substring with At Most Two Distinct Characters 求两个字母组成的最大子串长度 --------- java

最新文章

热门文章