My solution in java, three pointers, O(n) time


  • 0
    K

    I'd like to share my solution. There is no need to use hashmap to store the count of each char in the substring in this question. My solution uses another pointer to store the last position that we change char in substring. But my solution only works in k=2 situation. I like the hashmap solution better because it can extend to k situation.

    public int lengthOfLongestSubstringTwoDistinct(String s) {
        char[] chars = s.toCharArray();
        if(chars.length == 0){
            return 0;
        }
        int start = 0;
        int change = 0;
        Set<Character> temp = new HashSet<Character>();
        int max = 0;
        temp.add(chars[0]);
        int end = 1;
        while(end < chars.length){
            temp.add(chars[end]);
            if(chars[end] != chars[end - 1]){
                if(temp.size() > 2){
                    max = Math.max(max, end - start);
                    start = change;
                    temp.clear();
                    temp.add(chars[change]);
                    temp.add(chars[end]);
                }
                change = end;
            }
            ++end;
        }
        return Math.max(max, end - start);
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.