Find the length of the longest substring without repeating characters.

Example: Input: "abcca" Output: "abc"

Example: Input: "abdecbde" Output: "abdec"

The problem is similar to sliding window problem where we can have two counters start and end which maintains a window with no character repeated. To identify if a character is in the substring, we can use a Hashset that maintains characters visited in that window.

Slinding window using HashSet

 public int lengthOfLongestSubstring(String s) {
    int n = s.length();
    Set<e;Character>e; set = new HashSet();
    int ans = 0, i = 0, j = 0;
    while (i <e; n && j <e; n) {
        if (!set.contains(s.charAt(j))){
            set.add(s.charAt(j++));
            ans = Math.max(ans, j - i);
        }
        else {
            set.remove(s.charAt(i++));
        }
    }
    return ans;
}

Another alternate is to use an array which maintains the count of characters visited on the particular index.

Sliding window using Array

 public int lengthOfLongestSubstring(String s) {
	int end = 0, start = 0;
	int[] map = new int[128];
	int maxLen = 0;
	int counter = 0;
	while (end < s.length()) {
		if (map[s.charAt(end++)]++ > 0)
			counter++;
		while (counter > 0) {
			if (map[s.charAt(start++)]-- > 1)
				counter--;
		}
		maxLen = Math.max(maxLen, end - start);
	}
	return maxLen;
}

The time complexity of the above code is O(2n) = O(n). The can be further optimized by using HashMap which keeps the latest index of the character.

Optimizing Sliding window

 public int lengthOfLongestSubstring(String s) {
	Map<e;Character, Integer>e; map = new HashMap();
	int max = 0;
	for(int i =0 ; start=0, i < s.length(); i++) {
		char curr = s.charAt(i);
		if (map.containsKey(curr)) {
			start = Math.max(start, map.get(curr));
			
		}
		max = Math.max(max, i-start+1);
		map.put(curr, j+1);		
	}
	return max;
}

The time complexity of above solution is O(n). To optimize the memory HashMap can be replaced with an array.