Problem: Given a string, please get the length of the longest substring which does not have duplicated characters. Supposing all characters in the string are in the range from ‘a’ to ‘z’
Let’s denote the length of longest substring ending with the ith character by L(i).
We scan the string one character after another. When the ith character is scanned, L(i-1) is already know. If the ith character has not appeared before, L(i) should be L(i-1)+1. It’s more complex when the ith character is duplicated. Firstly we get the distance between the ith character and its previous occurrence. If the distance is greater than L(i-1), the character is not in longest substring without duplication ending with the (i-1)th character, so L(i) should also be L(i-1)+1. If the distance is less than L(i-1), L(i) is the distance, and it means between the two occurrence of the ith character there are no other duplicated characters.
public static int longestSubstringWithoutDuplication(String str) {
int curLength = 0;
int maxLength = 0;
int position[] = new int[26];
for(int i = 0; i < 26; ++i) {
position[i] = -1;
}
for(int i = 0; i < str.length(); ++i) {
int prevIndex = position[str.charAt(i) - 'a'];
if(prevIndex < 0 || i - prevIndex > curLength) {
++curLength;
}
else {
if(curLength > maxLength) {
maxLength = curLength;
}
curLength = i - prevIndex;
}
position[str.charAt(i) - 'a'] = i;
}
if(curLength > maxLength) {
maxLength = curLength;
}
return maxLength;
}
Read full article from Coding Interview Questions: No. 49 - Longest Substring without Duplication