Description:
Given a string s, find the length of the longest substring without repeating characters.
Examples:
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.Solution in Python:
To solve the problem of finding the length of the longest substring without repeating characters in a given string s, we can use a sliding window approach. This approach involves expanding and contracting a window to maintain a substring without duplicates, while keeping track of the maximum length encountered.
Python
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
# Initialize a set to store characters in the current window
char_set = set()
# Initialize pointers for the sliding window
left = 0
max_length = 0
# Iterate through the string with the right pointer
for right in range(len(s)):
# If the character at 'right' is in the set, it means there is a duplicate
# We need to move the 'left' pointer to the right to remove duplicates
while s[right] in char_set:
char_set.remove(s[left])
left += 1
# Add the current character to the set
char_set.add(s[right])
# Update the maximum length of substring found
max_length = max(max_length, right - left + 1)
return max_length
# Example usage:
# solution = Solution()
# print(solution.lengthOfLongestSubstring("abcabcbb")) # Output: 3
# print(solution.lengthOfLongestSubstring("bbbbb")) # Output: 1
# print(solution.lengthOfLongestSubstring("pwwkew")) # Output: 3Explanation:
- Initialization:
char_setis a set to store unique characters in the current window.leftis the start pointer of the current window.max_lengthis used to track the length of the longest substring found.
- Sliding Window:
- The
rightpointer iterates through the strings. - Inside the loop, if
s[right]is already inchar_set, we enter a while loop to remove characters fromchar_setstarting fromleftuntil the duplicate character is removed. - We then add
s[right]to the set and updatemax_lengthwith the length of the current window (right - left + 1).
- The
- Returning the Result:
- Finally, we return
max_length, which holds the length of the longest substring without repeating characters.
- Finally, we return
This solution efficiently finds the desired substring length with a time complexity of O(n), where n is the length of the string s, due to each character being processed at most twice (once added and once removed).
Solution in Javascript:
JavaScript
/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function(s) {
// Initialize a set to store characters in the current window
let charSet = new Set();
// Initialize pointers for the sliding window
let left = 0;
let maxLength = 0;
// Iterate through the string with the right pointer
for (let right = 0; right < s.length; right++) {
// If the character at 'right' is in the set, it means there is a duplicate
// We need to move the 'left' pointer to the right to remove duplicates
while (charSet.has(s[right])) {
charSet.delete(s[left]);
left++;
}
// Add the current character to the set
charSet.add(s[right]);
// Update the maximum length of substring found
maxLength = Math.max(maxLength, right - left + 1);
}
return maxLength;
};
// Example usage:
console.log(lengthOfLongestSubstring("abcabcbb")); // Output: 3
console.log(lengthOfLongestSubstring("bbbbb")); // Output: 1
console.log(lengthOfLongestSubstring("pwwkew")); // Output: 3Solution in Java:
Java
import java.util.HashSet;
public class Solution {
public int lengthOfLongestSubstring(String s) {
// Initialize a set to store characters in the current window
HashSet<Character> charSet = new HashSet<>();
// Initialize pointers for the sliding window
int left = 0;
int maxLength = 0;
// Iterate through the string with the right pointer
for (int right = 0; right < s.length(); right++) {
// If the character at 'right' is in the set, it means there is a duplicate
// We need to move the 'left' pointer to the right to remove duplicates
while (charSet.contains(s.charAt(right))) {
charSet.remove(s.charAt(left));
left++;
}
// Add the current character to the set
charSet.add(s.charAt(right));
// Update the maximum length of substring found
maxLength = Math.max(maxLength, right - left + 1);
}
return maxLength;
}
public static void main(String[] args) {
Solution solution = new Solution();
// Test cases
System.out.println(solution.lengthOfLongestSubstring("abcabcbb")); // Output: 3
System.out.println(solution.lengthOfLongestSubstring("bbbbb")); // Output: 1
System.out.println(solution.lengthOfLongestSubstring("pwwkew")); // Output: 3
}
}Solution in C#:
C#
using System;
using System.Collections.Generic;
public class Solution {
public int LengthOfLongestSubstring(string s) {
// Initialize a set to store characters in the current window
HashSet<char> charSet = new HashSet<char>();
// Initialize pointers for the sliding window
int left = 0;
int maxLength = 0;
// Iterate through the string with the right pointer
for (int right = 0; right < s.Length; right++) {
// If the character at 'right' is in the set, it means there is a duplicate
// We need to move the 'left' pointer to the right to remove duplicates
while (charSet.Contains(s[right])) {
charSet.Remove(s[left]);
left++;
}
// Add the current character to the set
charSet.Add(s[right]);
// Update the maximum length of substring found
maxLength = Math.Max(maxLength, right - left + 1);
}
return maxLength;
}
}