Table of contents
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.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.
Constraints:
0 <= s.length <= 5 * 104sconsists of English letters, digits, symbols and spaces.
Solutions:
Python:
class Solution(object):
def lengthOfLongestSubstring(self, s):
# Set to store the characters in the current window
window = set()
# Start and end indices of the current window
start = end = 0
# Length of the longest substring
longest = 0
while end < len(s):
# If the current character is not in the window, add it and move the end index
if s[end] not in window:
window.add(s[end])
end += 1
longest = max(longest, end - start)
# If the current character is already in the window, remove the start character and move the start index
else:
window.remove(s[start])
start += 1
return longest
or this way
class Solution(object):
def lengthOfLongestSubstring(self, s):
# Set up a dictionary to store the last index of each character
last_seen = {}
# Set up the start and end pointers for the sliding window
start = 0
end = 0
# Set up a variable to store the length of the longest substring
max_length = 0
# While the end pointer is within the bounds of the string
while end < len(s):
# If the character at the end pointer is not in the dictionary,
# or its last seen index is before the start of the current window
if s[end] not in last_seen or last_seen[s[end]] < start:
# Update the last seen index for the character
last_seen[s[end]] = end
# Move the end pointer to the right
end += 1
# Otherwise, if the character is already in the window
else:
# Update the max length with the current window length
max_length = max(max_length, end - start)
# Move the start pointer to the right, skipping the character at the last seen index
start = last_seen[s[end]] + 1
# Return the max length found, or the length of the current window
return max(max_length, end - start)
c#:
public class Solution {
public int LengthOfLongestSubstring(string s) {
// Set up a dictionary to store the last index of each character
var lastSeen = new Dictionary<char, int>();
// Set up the start and end pointers for the sliding window
int start = 0, end = 0;
// Set up a variable to store the length of the longest substring
int maxLength = 0;
// While the end pointer is within the bounds of the string
while (end < s.Length)
{
// If the character at the end pointer is not in the dictionary,
// or its last seen index is before the start of the current window
if (!lastSeen.ContainsKey(s[end]) || lastSeen[s[end]] < start)
{
// Update the last seen index for the character
lastSeen[s[end]] = end;
// Move the end pointer to the right
end++;
}
// Otherwise, if the character is already in the window
else
{
// Update the max length with the current window length
maxLength = Math.Max(maxLength, end - start);
// Move the start pointer to the right, skipping the character at the last seen index
start = lastSeen[s[end]] + 1;
}
}
// Return the max length found, or the length of the current window
return Math.Max(maxLength, end - start);
}
}
Java:
class Solution {
public int lengthOfLongestSubstring(String s) {
// Set up a map to store the last index of each character
Map<Character, Integer> lastSeen = new HashMap<>();
// Set up the start and end pointers for the sliding window
int start = 0, end = 0;
// Set up a variable to store the length of the longest substring
int maxLength = 0;
// While the end pointer is within the bounds of the string
while (end < s.length()) {
// If the character at the end pointer is not in the map,
// or its last seen index is before the start of the current window
if (!lastSeen.containsKey(s.charAt(end)) || lastSeen.get(s.charAt(end)) < start) {
// Update the last seen index for the character
lastSeen.put(s.charAt(end), end);
// Move the end pointer to the right
end++;
}
// Otherwise, if the character is already in the window
else {
// Update the max length with the current window length
maxLength = Math.max(maxLength, end - start);
// Move the start pointer to the right, skipping the character at the last seen index
start = lastSeen.get(s.charAt(end)) + 1;
}
}
// Return the max length found, or the length of the current window
return Math.max(maxLength, end - start);
}
}
Javascript:
/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function(s) {
// Initialize sliding window with left and right pointers
let left = 0;
let right = 0;
// Initialize a set to store the characters in the current window
const window = new Set();
// Initialize a variable to store the maximum length of the window
let maxLen = 0;
// Iterate through the string
while (right < s.length) {
// If the current character is not in the window, add it to the window and move the right pointer to the right
if (!window.has(s[right])) {
window.add(s[right]);
right++;
// Update the maximum length of the window if necessary
maxLen = Math.max(maxLen, right - left);
}
// If the current character is already in the window, remove the leftmost character from the window and move the left pointer to the right
else {
window.delete(s[left]);
left++;
}
}
// Return the maximum length of the window
return maxLen;
};
Typescript:
function lengthOfLongestSubstring(s: string): number {
// Initialize sliding window with left and right pointers
let left = 0;
let right = 0;
// Initialize a set to store the characters in the current window
const window = new Set<string>();
// Initialize a variable to store the maximum length of the window
let maxLen = 0;
// Iterate through the string
while (right < s.length) {
// If the current character is not in the window, add it to the window and move the right pointer to the right
if (!window.has(s[right])) {
window.add(s[right]);
right++;
// Update the maximum length of the window if necessary
maxLen = Math.max(maxLen, right - left);
}
// If the current character is already in the window, remove the leftmost character from the window and move the left pointer to the right
else {
window.delete(s[left]);
left++;
}
}
// Return the maximum length of the window
return maxLen;
};
PHP:
class Solution {
/**
* @param String $s
* @return Integer
*/
function lengthOfLongestSubstring($s) {
// Initialize sliding window with left and right pointers
$left = 0;
$right = 0;
// Initialize an array to store the characters in the current window
$window = [];
// Initialize a variable to store the maximum length of the window
$maxLen = 0;
// Iterate through the string
while ($right < strlen($s)) {
// If the current character is not in the window, add it to the window and move the right pointer to the right
if (!in_array($s[$right], $window)) {
$window[] = $s[$right];
$right++;
// Update the maximum length of the window if necessary
$maxLen = max($maxLen, $right - $left);
}
// If the current character is already in the window, remove the leftmost character from the window and move the left pointer to the right
else {
array_shift($window);
$left++;
}
}
// Return the maximum length of the window
return $maxLen;
}
}
To have more solutions to LeetCode problems just visit my article here on medium https://medium.com/@araneznorman