Given a string s, find the length of the longest substring without repeating characters.
Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
- 0 <= s.length <= 5 * 104
- s consists of English letters, digits, symbols and spaces.
class Solution {
public int lengthOfLongestSubstring(String s) {
int[] chars = new int[128];
int left = 0;
int right = 0;
int res = 0;
while (right < s.length()) {
char r = s.charAt(right);
chars[r]++;
while (chars[r] > 1) {
char l = s.charAt(left);
chars[l]--;
left++;
}
res = Math.max(res, right - left + 1);
right++;
}
return res;
}
}
The above solution is for the "Longest Substring Without Repeating Characters" problem using the sliding window technique. It efficiently finds the length of the longest substring without repeating characters within a given string s
. Here's how the code works:
lengthOfLongestSubstring
function takes a string s
as input and returns an integer representing the length of the longest substring without repeating characters.chars
of size 128 to keep track of character occurrences.left
and right
pointers represent the sliding window. left
points to the start of the current substring, and right
points to the end.res
keeps track of the length of the longest substring without repeating characters.right
pointer is within the bounds of the string s
.right
is fetched from the string.chars
array.while (chars[r] > 1)
) runs while the character count becomes greater than 1 (indicating a repeating character). In this loop:
left
is fetched.chars
array.left
pointer is moved one step to the right.right - left + 1
) is compared with the current res
, and the maximum value is stored in res
.right
pointer is moved one step to the right.res
.The sliding window technique allows the algorithm to efficiently find the longest substring without repeating characters by maintaining a sliding window with unique characters. The code is well-structured and effectively solves the problem.
Please note that the code assumes that the input string s
only consists of ASCII characters, which is why an array of size 128 is used.