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

Question

Given a string s,find the length of the longest substring
without repeating characters. Click here to open question in Leetcode

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))) {
                hs.add(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++;
                hs.add(s.charAt(r));
            }
        }

        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