3. Longest Substring Without Repeating Characters (Medium)
https://leetcode.com/problems/longest-substring-without-repeating-characters/
Given a string, find the length of the longest substring without repeating characters.
Example 1:
Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc"
, with the length of 3.
Example 2:
Input: "bbbbb"
Output: 1
Explanation: The answer is "b"
, with the length of 1.
Example 3:
Input: "pwwkew" Output: 3 Explanation: The answer is"wke"
, with the length of 3. Note that the answer must be a substring,"pwke"
is a subsequence and not a substring.
Solutions
class Solution {
// Non-Repeating Character Substring (NRCS)
// This problem solving idea is ingenious that it reduce the time complexity from O(n^2) to O(n)
// with the use of an array which is used to keep track of the last index of the given char.
// Walk through the array, at one point, you visit char x, if you find x not appears before, you
// could deems it as a non-repeating substring. If it occurs previously, there are following two
// situations.
// 1. Take string "abcdefgc" as an example, when pointer locates at the tail char 'c', you will find
// there is another 'c' at index 2, so the max length non-repeating substring is defgc.
// 2. Take string "abcddefgc" as an example, pointer still locates at the tail char 'c', precious 'c'
// at index 2. However, the max length non-repeating substring turns to be defgc. The reason is that
// the counting work starts from the second d because of the prior repeated d.
// To sum up, when you meet a repeating char, it is not a must to start over the counting, which
// depends on the specific cases.
public int lengthOfLongestSubstring(String str) {
if (str == null || str.length() == 0) {
return 0;
}
int len = str.length();
int[] visited = new int[256];
// Initialize the visited array as -1, -1 is used to indicate that character has not been visited yet.
Arrays.fill(visited, -1);
// length of max NRCS substring
int maxLen = 0;
// previous index
int prevIndex;
// length of current NRCS substring
int curLen = 0;
for (int i = 0; i < len; i++) {
prevIndex = visited[str.charAt(i)];
// Current character is not present in the already processed substring.
if (prevIndex == -1) {
curLen++;
}
// It is not part of the current NRCS, ignore it and increase curLen
else if (i - curLen > prevIndex) {
curLen++;
}
// If the current character is present in currently considered NRCS, then update NRCS
// to start from the next character of the prevIndex.
else {
curLen = i - prevIndex;
}
// Also, when we are changing the NRCS, we should also check whether length of the previous
// NRCS is greater than maxLen or not.
if (curLen > maxLen) {
maxLen = curLen;
}
// update the index of current character
visited[str.charAt(i)] = i;
}
return maxLen;
}
}
Incorrect Solutions
class Solution {
// This solution exceeds the time limit.
// Walk through all the possible length from 2 to s.length(). Use a HashMap to keep the length and
// possible ranges.
public int lengthOfLongestSubstring(String s) {
if (s == null || s.length() == 0) {
return 0;
}
int len = s.length();
Map<String, Integer> visited = new HashMap<>();
for (int i = 0; i < len; i++) {
visited.put(i + "#" + i, 1);
}
// Window size starts from 2 to len
for (int ws = 2; ws <= len; ws++) {
// Iterate the chars from 0, and the window tail should not exceed i+wws-1
for (int i = 0; i < len - ws + 1; i++) {
// Window [i,i+ws-2] is a preceding window that 1 element less than current
// window [i, i+ws-1]. If preceding window contains duplicates, it indicates
// current window also has.
String pw = i + "#" + (i + ws - 2);
if (!visited.containsKey(pw)) {
continue;
}
String cw = i + "#" + (i + ws - 1);
// s.substring(start, end) where end is exclusive
if (!s.substring(i, i + ws - 1).contains(s.charAt(i + ws - 1) + "")) {
// if doesn't contain duplicates, increase the distinct char number
visited.put(cw, visited.get(pw) + 1);
}
}
}
int max = 0;
for (String key : visited.keySet()) {
if (visited.get(key) > max) {
max = visited.get(key);
}
}
return max;
}
}