## DEV Community

Leetcode

Posted on • Updated on

# Solving the "Longest Substring Without Repeating Characters" Problem on LeetCode

## Question

Given a string `s`,find the length of the longest substring

## Question type:

Medium,

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.
``````

## Approach:

To find the length of the longest substring without repeating characters, we can use a sliding window approach. We'll maintain two pointers, l and r, which represent the left and right ends of the current substring. We'll also use a HashSet to keep track of the characters in the current substring.

Here's the step-by-step explanation of the approach:

Initialize two pointers, l and r, to 0. Initialize a HashSet hs to store characters in the current substring, and maxi to store the maximum length found so far.

Start iterating through the input string s from left to right (increment r):

a. If s.charAt(r) is not in the HashSet hs, it means we can extend the current substring. So, add s.charAt(r) to hs and update maxi to be the maximum of its current value and r - l + 1 (the length of the current substring).

b. If s.charAt(r) is already in hs, it means we have a repeating character. We need to shrink the substring by incrementing l and removing s.charAt(l) from hs until there are no repeating characters. This step ensures that we maintain a substring without repeating characters.

Continue this process until r reaches the end of the string.

Finally, return maxi, which represents the length of the longest substring without repeating characters.

## Java Code:

Here's the Java code that implements the above approach:

``````class Solution {
public int lengthOfLongestSubstring(String s) {
HashSet<Character> hs = new HashSet<>();
int maxi = 0;
int l = 0;

for (int r = 0; r < s.length(); r++) {
if (!hs.contains(s.charAt(r))) {
maxi = Math.max(maxi, r - l + 1);
} else {
while (s.charAt(l) != s.charAt(r)) {
hs.remove(s.charAt(l));
l++;
}
hs.remove(s.charAt(l));
l++;
}
}

return maxi;
}
}
``````

## Time Complexity:

The time complexity of this solution is O(N), where N is the length of the input string s. This is because we traverse the string once, and for each character, we perform constant-time operations (addition/removal from HashSet and comparisons). Therefore, the overall time complexity is linear.

Happy coding,
shiva