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 Setset = 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_len
var 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_sethash_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; HashSetset = 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; } }