Solution For Longest Substring Without Repeating Characters
Problem statement:
Given a string s, find the length of the longest substring without repeating characters.
Example 1:
Input: s = “abcabcbb”
Output: 3
Explanation: The answer is “abc”, with the length of 3.
Example 2:
Input: s = “bbbbb”
Output: 1
Explanation: The answer is “b”, with the length of 1.
Example 3:
Input: s = “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.
Solution:
To find the longest substring without repeating characters, we can use the sliding window approach. In this approach, we maintain a sliding window of characters in the string, and keep track of the characters we have already seen in a set.
We start with an empty set, an empty substring, and the start of the window at the beginning of the string. We then move the end of the window forward until we find a repeating character. When we encounter a repeating character, we remove the first character of the substring from the set and move the start of the window forward. We keep track of the length of the longest substring we have seen so far.
Here is the Python code for the solution:
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
seen = set()
start = 0
max_len = 0
for end in range(len(s)):
while s[end] in seen:
seen.remove(s[start])
start += 1
seen.add(s[end])
max_len = max(max_len, end-start+1)
return max_len
We initialize an empty set seen to keep track of the characters we have already seen, and start at the beginning of the string with the start of the window set to 0. We also initialize the maximum length of the substring seen so far to 0.
We then loop through the string, with end as the index of the end of the window. We add the character at the end of the window to the set seen, and update the maximum length of the substring seen so far if necessary.
If the character at the end of the window is already in seen, we remove the first character of the substring (at the start of the window) from seen and move the start of the window forward. We repeat this until the character at the end of the window is not in seen anymore.
Finally, we return the maximum length of the substring seen so far.
Time Complexity:
The time complexity of this solution is O(n), where n is the length of the input string s. We process each character in the string once, and the set operations take constant time on average.
Space Complexity:
The space complexity of this solution is O(min(n, m)), where n is the length of the input string s and m is the size of the character set (26 for English alphabet). In the worst case, the input string contains all unique characters, so the space complexity is O(n). In the best case, the input string contains only one character, so the space complexity is O(1).
Step by Step Implementation For Longest Substring Without Repeating Characters
public class Solution {
public int lengthOfLongestSubstring(String s) {
// base case
if (s == null || s.length() == 0) {
return 0;
}
// use a set to keep track of all the unique characters in the current substring
Set set = new HashSet<>();
// use two pointers to keep track of the start and end of the current substring
int start = 0;
int end = 0;
// use a variable to keep track of the maximum length substring
int maxLength = 0;
// loop through the string
while (end < s.length()) {
// if the character at the end index is not in the set
if (!set.contains(s.charAt(end))) {
// add it to the set
set.add(s.charAt(end));
// increment the end pointer
end++;
// update the maximum length
maxLength = Math.max(maxLength, end - start);
}
// if the character is already in the set
else {
// remove the character at the start index from the set
set.remove(s.charAt(start));
// increment the start pointer
start++;
}
}
// return the maximum length
return maxLength;
}
} class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
# Base case: empty string has length 0
if (len(s) == 0):
return 0
# Initialize hash set and max length
hash_set = set()
max_len = 0
# Iterate through string, keeping track of start index of current substring
start = 0
for i in range(len(s)):
# If current character is not in hash set, add it and update max length if necessary
if (s[i] not in hash_set):
hash_set.add(s[i])
max_len = max(max_len, i - start + 1)
# If current character is in hash set, update start index to be the index after the last instance of the repeated character
else:
while (s[start] != s[i]):
hash_set.remove(s[start])
start += 1
start += 1
return max_lenvar lengthOfLongestSubstring = function(s) {
let hash = {};
let max = 0;
let start = 0;
for(let i = 0; i < s.length; i++) {
let char = s[i];
if(hash[char] >= start) {
start = hash[char] + 1;
}
hash[char] = i;
max = Math.max(max, i - start + 1);
}
return max;
};The following is a C++ solution for the leetcode problem longest-substring-without-repeating-characters:
int lengthOfLongestSubstring(string s) {
int n = s.length();
int i = 0, j = 0;
int max_len = 0;
unordered_set hash_set;
while (i < n && j < n) {
// If the current character is not in the hash set,
// add it to the hash set and move on to the next character
if (hash_set.find(s[j]) == hash_set.end()) {
hash_set.insert(s[j]);
j++;
max_len = max(max_len, j - i);
}
// If the current character is in the hash set,
// remove the previous character from the hash set
// and move on to the next character
else {
hash_set.erase(s[i]);
i++;
}
}
return max_len;
} public class Solution {
public int LengthOfLongestSubstring(string s) {
if (s == null || s.Length == 0) return 0;
HashSet set = new HashSet();
int max = 0, i = 0, j = 0;
while (i < s.Length && j < s.Length) {
// try to extend the range [i, j]
if (!set.Contains(s[j])) {
set.Add(s[j++]);
max = Math.Max(max, j - i);
} else {
set.Remove(s[i++]);
}
}
return max;
}
}