Java solution using LinkedList. Accepted.


  • 1
    P

    I decided to use a LinkedList to hold the latest sequence. If the next char in string exist in sequence we cut it from begin to founded char.

    public int lengthOfLongestSubstring(String s) {
    	int max = 0;
        char[] chars = s.toCharArray();
    	LinkedList<Character> seq = new LinkedList<Character>();
    	for (int i=0; i<chars.length; i++) {
    		if (seq.contains(chars[i])) {
    			if (max < seq.size()) {
    				max = seq.size();
    			}
    			while (seq.removeFirst() != chars[i]);
    		}
    		seq.add(chars[i]);
    	}
    	if (max < seq.size()) {
    		max = seq.size();
    	}
    	return max;
    }

  • 0
    S

    Is this code O(n^2)?

    Because seq.contains() might cause O(n) time.


Log in to reply
 

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