O(n) solution using HashMap JAVA


  • 0
    R

    the idea is to store the last occurrence of the characters and use dynamic window to determine the length of the subsequence.

    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.isEmpty()) {
            return 0;
        }
        int maxLength = 0;
        int startIndex = 0;
        HashMap<Character, Integer> lastApperance = new HashMap<Character, Integer>();
        for (int i = startIndex; i < s.length(); i++) {
            if (lastApperance.containsKey(s.charAt(i))) {
                int len = i - startIndex;
                if (len > maxLength) {
                    maxLength = len;
                } 
                if ((lastApperance.get(s.charAt(i))  + 1) > startIndex) {
                    startIndex = lastApperance.get(s.charAt(i)) + 1;
                }
            } 
            lastApperance.put(s.charAt(i), i);
        } 
        if ((s.length() - startIndex) > maxLength) {
            maxLength = s.length() - startIndex;
        }
        return maxLength;
    }

Log in to reply
 

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