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 :
3Time Complexity of Above solution is O(n) while space complexity is O(n) in the worst case.
