Length of the longest substring without repeating characters

Given a string s, the task is to find the length of the longest substring without repeating characters.

Input: s = "cabcabcbb"
Output: 3

Input: s = "aaaaa"
Output: 1

Input: s = "zpwwke"
Output: 3

Solutions

Method 1: In O(n^2) time and O(n) space

This problem can be solved in O(n^2) time and O(n) space with the help of a hash.

The idea is to use two nested loops and check for every substring.

Use a HashSet to identify if the current substring has a repeating character.

	package com.cb.string;

	import java.util.HashSet;
	import java.util.Set;

	/*
	* Time complexity: O(n*n)
	* Space complexity: O(n) -- reset and not accumulating
	* */
	public class S18_LongestSubstringWithoutRepeatingCharacters_n2_and_n {
	private static int longestSubstring(String s) {
	int n = s.length();
	int longestSoFar = 0;
	for (int i = 0; i < n; i++) {
	Set<Character> set = new HashSet<>();
	for (int j = i; j < n; j++) {
	char c = s.charAt(j);
	if (!set.contains(c)) {
	set.add(c);
	longestSoFar = Math.max(set.size(), longestSoFar);
	} else {
	break;
	}
	}
	}
	return longestSoFar;
	}

	public static void main(String[] args) {
	String s = "zpwwke";
	System.out.println(longestSubstring(s));// 3
	}
	}

view raw S18_LongestSubstringWithoutRepeatingCharacters_n2_and_n.java hosted with ❤ by GitHub

Complexity

The time complexity of this solution is O(n^2) and the space complexity is O(n).

Method 2: In O(n) time and O(n) space

This problem can be solved in O(n) time and O(n) space with the help of a sliding window.

The idea is to maintain a sliding window from the i^th to the j^th index.

Use a HashMap to identify if the current window has a repeating character. This map contains a character as a key and the character's index in the array as a value.

If a repeating character is found at the j^th index, look up the index of an already existing duplicate character in the map and move i to the next of this index.

While checking for repeating characters in a map, make sure that the repeating character is in the current window (at >=i^th index).

Keep incrementing the j^th index until it is less than or equals the last index and the character at the j^th index is not repeating.

In each iteration, if the length of the sliding window, i.e., "lengthTillHere," is greater than "lengthSoFar," update lengthSoFar = lengthTillHere.

	package com.cb.string;

	import java.util.HashMap;
	import java.util.Map;

	/*
	* Time complexity: O(n)
	* Space complexity: O(1)
	* */
	public class S18_LongestSubstringWithoutRepeatingCharacters_sliding_window {

	private static int longestSubstring(String s) {
	int n = s.length();

	// value and index
	Map<Character, Integer> map = new HashMap<>();
	int i = 0, j = 0;
	int lengthSoFar = 0, lengthTillHere = 0;

	while (i < n && j < n) {
	char c = s.charAt(j);
	// not before window start
	if (map.containsKey(c) && map.get(c) >= i) {

	// new window start
	i = map.get(c) + 1;

	// change index to new element
	map.put(c, j);

	// new window length so far
	lengthTillHere = j - i + 1;
	} else {
	// add new element
	map.put(c, j);
	lengthTillHere += 1;
	lengthSoFar = Math.max(lengthSoFar, lengthTillHere);
	}
	j++;
	}
	return lengthSoFar;
	}

	public static void main(String[] args) {
	String s = "dvdf";
	System.out.println(longestSubstring(s));// false
	}
	}