O(n) Java solution -- runtime 16ms


  • 0
    Z
    public class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, ListNode> substring = new HashMap<>();
        char[] sArray = s.toCharArray();
        int len = 0;
        ListNode p = null;
        for (int i=0; i < sArray.length; i++) {
            char curChar = sArray[i];
            ListNode dupe = substring.get(curChar);
            ListNode newChar = null;
            if (dupe != null) { // found dupe char
                // count
                len = substring.size() > len ? substring.size() : len;
                
                newChar = dupe;
                
                // remove all the prev characters
                if (dupe.prev != null) {
                    ListNode q = dupe.prev;
                    dupe.prev = null; // reset the left pointer
                    while (true) {
                        substring.remove(q.val);
                        if (q.prev != null) {
                            q = q.prev;
                        } else {
                            break;
                        }
                    }    
                }
                
                // define the new left
                if (dupe.next != null) {
                    dupe.next.prev = null;
                    dupe.next = null;
                }
            } else { // it is a new char
                newChar = new ListNode(curChar);
                substring.put(curChar, newChar);
            }
    
            if (p == null) { // the first char
                p = newChar;
            } else if (p == newChar) { // pointing to itself
                // do nothing
            } else {
                p.next = newChar;
                p.next.prev = p;
                p = p.next;
            }
        }
        len = substring.size() > len ? substring.size() : len;
        return len;
    }
    
    public class ListNode {
        char val;
        ListNode prev;
        ListNode next;
        ListNode(char v) {
            val = v;
        }
    }
    

    }


Log in to reply
 

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