Simple O(n) java solution - easily extend to k characters


  • 54
    K

    The main idea is to maintain a sliding window with 2 unique characters. The key is to store the last occurrence of each character as the value in the hashmap. This way, whenever the size of the hashmap exceeds 2, we can traverse through the map to find the character with the left most index, and remove 1 character from our map. Since the range of characters is constrained, we should be able to find the left most index in constant time.

    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;
        }
    }

  • 5
    S

    shouldn't this solution be O(nk) in time complexity?


  • 1
    W

    k = 2 in this case. So O(kn) = O(2n) = O(n)


  • 11
    G

    Great solution! I reimplemented it with concise code.

    public int lengthOfLongestSubstringTwoDistinct(String s) {
        Map<Character, Integer> lastSeen = new HashMap<>();
        int low = 0, max = 0;
        for (int i = 0; i < s.length(); i++) {
            lastSeen.put(s.charAt(i), i);
            if (lastSeen.size() > 2) {
                int toRemoveLastSeen = i;
                for (Integer val : lastSeen.values()) toRemoveLastSeen = Math.min(val, toRemoveLastSeen);
                lastSeen.remove(s.charAt(toRemoveLastSeen));
                low = toRemoveLastSeen + 1;
            }
            max = Math.max(max, i - low + 1);
        }
        return max;
    }
    

  • 0
    F
    This post is deleted!

  • 0
    P

    Good solution. Use LinkedHashMap for better code.


  • 0
    R

    Iterating the map every time sounds pretty inefficient and unnecessary. You can keep two variables to save the chars with the leftmost index and rightmost index, so that you can directly access those in O(1) time.


  • 1

    Two pointer solution avoids all the hashing and will run quicker.

        public int LengthOfLongestSubstringTwoDistinct(string s) 
        {
            int left1 = -1;
            int left2 = -1;
            int len = 0;
            int max = 0;
            for (int i = 0; i < s.Length; i++)
            {
                if (left1 == -1 || s[i] == s[left1]) 
                {
                    left1 = i;
                    len++;
                    max = Math.Max(max, len);
                }
                else if (left2 == -1 || s[i] == s[left2]) 
                {
                    left2 = i;
                    len++;
                    max = Math.Max(max, len);
                }
                else
                {
                    if (left1 < left2) { len = i - left1; left1 = i; }
                    else { len = i - left2; left2 = i; }
                }
            }
            return max;
        }
    

  • 0
    C

    @kevinhsu said in Simple O(n) java solution - easily extend to k characters:

    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;
    }
    }

    What if Interviewer had asked to return the actual substring rather than just the length?


  • 0
    C
    This post is deleted!

Log in to reply
 

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