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.


Recommend Reading

  1. How java manages Memory?
  2. Why is it advised to use hashcode and equals together?
  3. Comparable and Comparator in java
  4. How to create Singleton class in Java?
  5. Difference between equals and ==?
  6. When to use abstract class over interface?
  7. Difference between final, finally and finalize
  8. Why is it recommended to use Immutable objects in Java