Problem:
Given a string, find the length of the longest substring without repeating characters.For Example:
Input: "xxyzxzzy"
Output: 3
Explanation: The answer is "xyz", with the length of 3.
Input: "mmmmmm"
Output: 1
Explanation: The answer is "m", with the length of 1.
Example 3:
Input: "hmmqmym"
Output: 3
Explanation: The answer is "qmy", with the length of 3.
Solution:
We can use a sliding window, find all the combinations of the end index and start index, check if substring(start, end) have duplicate character, the start and end index need two loops, check duplicate need another loop. The total cost will be O(N^3).
We can do this smarter.
The duplicate check can be done with a HashMap, which has cost of 1 instead of N.
If substring [start, end) has already been checked for duplicate, then to check duplicate for substring [start, end + 1) is to check if the character at index end is already in the substring [start, end), which is a cost 1 HashMap call.
Anther observation is: if a character has duplicate at index k in the range [i, j), the start index can advance to k + 1, skip all the duplicate check between [i, k]. The reason is, any substring start before k, will bound to find duplicate at current examine index, the only chance for no duplicate substring start at k + 1.
We can do this smarter.
The duplicate check can be done with a HashMap, which has cost of 1 instead of N.
If substring [start, end) has already been checked for duplicate, then to check duplicate for substring [start, end + 1) is to check if the character at index end is already in the substring [start, end), which is a cost 1 HashMap call.
Anther observation is: if a character has duplicate at index k in the range [i, j), the start index can advance to k + 1, skip all the duplicate check between [i, k]. The reason is, any substring start before k, will bound to find duplicate at current examine index, the only chance for no duplicate substring start at k + 1.
import java.util.*;
class FindLongestSubString {
//abbcprqmpaq
private static String getLongest(String word) {
//sliding window, advance start index and end index
Map<Character, Integer> nextPos = new HashMap<>();
int maxLength = 0;
int startIndex = 0;
for(int start = 0, end = 0; end < word.length(); end++) { //end = 10q
if(nextPos.containsKey(word.charAt(end))) {
start = Math.max(start, nextPos.get(word.charAt(end))); //7
}
if(end - start + 1 > maxLength) { //6
maxLength = end - start + 1; //6
startIndex = start; //2
}
nextPos.put(word.charAt(end), end + 1); //a10;b3;c4;p9;r6;q11;m8
}
return word.substring(startIndex, startIndex + maxLength);
}
public static void main(String...args) {
String result = getLongest("abbcprqmpaq");
System.out.println(result);
result = getLongest("abbcprqmpaqx");
System.out.println(result);
result = getLongest("abbcrqmppaqx");
System.out.println(result);
result = getLongest("abbcprqmpazx");
System.out.println(result);
result = getLongest("mznhieabbcprqmpazx");
System.out.println(result);
}
}
class FindLongestSubString {
//abbcprqmpaq
private static String getLongest(String word) {
//sliding window, advance start index and end index
Map<Character, Integer> nextPos = new HashMap<>();
int maxLength = 0;
int startIndex = 0;
for(int start = 0, end = 0; end < word.length(); end++) { //end = 10q
if(nextPos.containsKey(word.charAt(end))) {
start = Math.max(start, nextPos.get(word.charAt(end))); //7
}
if(end - start + 1 > maxLength) { //6
maxLength = end - start + 1; //6
startIndex = start; //2
}
nextPos.put(word.charAt(end), end + 1); //a10;b3;c4;p9;r6;q11;m8
}
return word.substring(startIndex, startIndex + maxLength);
}
public static void main(String...args) {
String result = getLongest("abbcprqmpaq");
System.out.println(result);
result = getLongest("abbcprqmpaqx");
System.out.println(result);
result = getLongest("abbcrqmppaqx");
System.out.println(result);
result = getLongest("abbcprqmpazx");
System.out.println(result);
result = getLongest("mznhieabbcprqmpazx");
System.out.println(result);
}
}
The time complexity is O(N), we need to iterate the word, cost for hashmap is 1. The space complexity is O(N) which is the size of the hashMap
This is a typical sliding window problem, we use a mask to hide the whole string, only reveal a window for part of the string, then study its property. The sliding window has a left and right edge, we move the left edge to mask unconcerned characters, we move the right edge to reveal more character into concern. For this particular problem, we move the right edge 1 step at a time to reveal one more character until visited the whole string. If the new character has been seen before at index k, we can safely move left edge to k+1, ignoring all the substrings before position k. It is because any substring that includes the same character at index k will have duplicate. Now the substring in the sliding window's left and right edge form a candidate for the longest substring without duplicate. To remember the last time we saw a character, we can use a HashMap, however, since the characters are limited, we can use an array for the same purpose, size 128 array for ASCII and 256 for extended ASCII.
public class Solution {
public static String longestSubString(String str) { //x
String longest = "";
int[] lastSeen = new int[256];
int i = 0, j = 0;
while(j < str.length()) { //i=2, j=5
Character c = str.charAt(j++); //x
i = Math.max(i, lastSeen[c]);
lastSeen[c] = j; //x:5, y:3, z= 4
if(longest.length() < j - i) {
longest = str.substring(i, j); //xyz
}
}
return longest;
}
public static void main(String...args) {
System.out.println(longestSubString("xxyzxzzy"));
}
}
public static String longestSubString(String str) { //x
String longest = "";
int[] lastSeen = new int[256];
int i = 0, j = 0;
while(j < str.length()) { //i=2, j=5
Character c = str.charAt(j++); //x
i = Math.max(i, lastSeen[c]);
lastSeen[c] = j; //x:5, y:3, z= 4
if(longest.length() < j - i) {
longest = str.substring(i, j); //xyz
}
}
return longest;
}
public static void main(String...args) {
System.out.println(longestSubString("xxyzxzzy"));
}
}
The time complexity is O(N), we only go through the array once. The space complexity is O(N), the longest substring can only be as long as N.
