Example: Input: "abcca" Output: "abc"
Example: Input: "abdecbde" Output: "abdec"
The problem is similar to sliding window problem where we can have two counters start
and end
which maintains a window with no character repeated. To identify if a character is in the substring, we can use a Hashset that maintains characters visited in that window.
public int lengthOfLongestSubstring(String s) {
int n = s.length();
Set<e;Character>e; set = new HashSet();
int ans = 0, i = 0, j = 0;
while (i <e; n && j <e; n) {
if (!set.contains(s.charAt(j))){
set.add(s.charAt(j++));
ans = Math.max(ans, j - i);
}
else {
set.remove(s.charAt(i++));
}
}
return ans;
}
Another alternate is to use an array which maintains the count of characters visited on the particular index.
public int lengthOfLongestSubstring(String s) {
int end = 0, start = 0;
int[] map = new int[128];
int maxLen = 0;
int counter = 0;
while (end < s.length()) {
if (map[s.charAt(end++)]++ > 0)
counter++;
while (counter > 0) {
if (map[s.charAt(start++)]-- > 1)
counter--;
}
maxLen = Math.max(maxLen, end - start);
}
return maxLen;
}
The time complexity of the above code is O(2n) = O(n)
. The can be further optimized by using HashMap which keeps the latest index of the character.
public int lengthOfLongestSubstring(String s) {
Map<e;Character, Integer>e; map = new HashMap();
int max = 0;
for(int i =0 ; start=0, i < s.length(); i++) {
char curr = s.charAt(i);
if (map.containsKey(curr)) {
start = Math.max(start, map.get(curr));
}
max = Math.max(max, i-start+1);
map.put(curr, j+1);
}
return max;
}
The time complexity of above solution is O(n). To optimize the memory HashMap can be replaced with an array.
Recommend Reading