# O(n) Java solution with detailed explanation

• We use a HashMap to store characters and the corresponding updated index. Loop from the first character to the last character of the string. Everytime when a duplication is detected, the length is calculated by using the current index i minors the dupNextIndex, and the dupNextIndex is updated.

For example, abcdbcdcd.
At first dupNextIndex = 0, in the loop of second b, a duplication pairs b is detected, then dupNextIndex is set to be 2 (the next character of the first b). In the loop of second c, a duplication pairs c is detected, then dupNextIndex is set to be 3 (the next character of the first c), etc. When update dupNextIndex, note that we use dupNextIndex = Math.max(hash.get(c) + 1, dupNextIndex) instead of dupNextIndex = hash.get(c) + 1 to avoid that the dupNextIndex goes back.

At last, we need to deal with the case when the longest substring is at the end of the string.

``````public class Solution {
public int lengthOfLongestSubstring(String s) {

if (s == null || s.length() == 0)
return 0;

int maxLen = 1;
int dupNextIndex = 0;
HashMap<Character, Integer> hash = new HashMap<Character, Integer>();

for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (hash.containsKey(c)) {
maxLen = Math.max(maxLen, i - dupNextIndex);
dupNextIndex = Math.max(hash.get(c) + 1, dupNextIndex);
}
hash.put(c, i);
}

maxLen = Math.max(maxLen, s.length() - dupNextIndex);

return maxLen;
}
}``````

• smart!
reading your codes need to think carefully

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.