Find Longest Sub-string without any Repeating characters.

A substring is a contiguous sequence of characters within a string. For instance, "the best of" is a substring of "It was the best of times". This is not to be confused with subsequence, which is a generalization of a substring. For example, "Itwastimes" is a subsequence of "It was the best of times", but not a substring.

Prefix and suffix are special cases of a substring. A prefix of a string {\displaystyle S} S is a substring of {\displaystyle S} S that occurs at the beginning of {\displaystyle S} S. A suffix of a string {\displaystyle S} S is a substring that occurs at the end of {\displaystyle S} S.

The list of all substrings of the string "apple" would be "apple", "appl", "pple", "app", "ppl", "ple", "ap", "pp", "pl", "le", "a", "p", "l", "e", "".

import java.util.HashMap;

public class LongestSubstringWithoutRepeatingCharacters {

	public static void main(String[] args) {
		String str = "abcabcbb";
		HashMap<Character,Integer> map = new HashMap<Character,Integer>();
		int maxLen = 0;
		for(int i=0;i<str.length();i++) {
			if(map.containsKey(str.charAt(i))) {
				if((i - map.get(str.charAt(i))) > maxLen) {
					maxLen = i - map.get(str.charAt(i));
				}
				map.put(str.charAt(i), i);
			}
			else
				map.put(str.charAt(i), i);
		}
		
		System.out.println(maxLen);

	}

}

Output :

3

Time Complexity of Above solution is O(n) while space complexity is O(n) in the worst case.