Java solution using moving window, O(n) with full comments


  • 1
    public class Solution {
        public int lengthOfLongestSubstring(String input) {
            // parse string to array for easy access in Java
            char[] s = input.toCharArray();
            
            // array for count each letter in s for check duplicate
            // letter c have counter[c] > 1 mean c is dupplicated
            int[] counter = new int[300];
            
            int answer = 0;
            
            // initial window
            int left = 0;
            int right = 0;
            
            while (right < s.length) {
                // increase total letter at index right in window by 1
                counter[s[right]]++;
                
                // while current letter duplicate
                // we move left until this letter unique
                while (counter[s[right]] > 1) {
                    counter[s[left]]--;
                    left++;
                }
                
                // update our answer
                answer = Math.max(answer, right - left + 1);
                
                // move right window
                right++;
            }
            
            return answer;
        }
    }
    

Log in to reply
 

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