Java O(n) solution, sliding window using a queue


  • 0
    U

    Sliding Window solution. O(n)

    public class Solution {
    	public int lengthOfLongestSubstring(String s) {
    		Queue<Character> q = new LinkedList<Character>();
    		int len = s.length(), l = 0, r = 0, max = 0, localMax = 0;
    
    		for (; l <= r && r < len; r++) {
    			if (q.contains(s.charAt(r))) {		// current item was in the window
    				while (q.peek() != s.charAt(r) && l < r) {
    					q.poll();
    					l++;
    					localMax--;
    				}
    				q.poll(); 	// remove the 1st occurrence of s.charAt(r)
    				l++;
    			} else			// current item was not in the window
    				localMax++;
    
    			q.offer(s.charAt(r));	// enqueue current char
    			max = (max < localMax) ? localMax : max;
    		}
    		return max;
    	}
    }
    

Log in to reply
 

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