Solving the Longest Substring Without Repeating Characters (LeetCode #3)

In this post, we’ll dive into one of the most common interview questions: “Longest Substring Without Repeating Characters” (LeetCode #3). This problem challenges you to find the length of the longest substring without repeating characters from a given string. It’s an excellent exercise to practice the sliding window technique, which is often used in string manipulation problems.

---

Solution Approach:

The task is simple: Given a string s, we need to find the length of the longest substring without repeating characters. You can read full description in LeetCode.

Example:

Input: s = "abcabcbb"

Output: 3

Explanation: The longest substring without repeating characters is "abc", with a length of 3. Other substrings like "bca" or "cab" also satisfy the condition.

Solution Approach:

We solve this problem using the Sliding Window technique. Here’s the basic idea:

1. We maintain two pointers (leftP and rightP), which represent the current window of the substring we’re exploring.
2. As we slide the window from left to right, we keep track of the characters we encounter using an array called seen to store the last seen index of each character.
3. Whenever we encounter a repeating character, we adjust the left pointer to move past the last occurrence of the repeated character.
4. Throughout this process, we keep track of the maximum length of any valid substring.

---

Code Implementation:

javaCopy codeclass Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s.isEmpty()) {
            return 0;
        }

        int length = s.length();
        int[] seen = new int[128];  // Array to track last seen positions of characters
        Arrays.fill(seen, -1);  // Initialize array with -1
        seen[s.charAt(0)] = 0;
        int maxLength = 1, leftP = 0;

        for (int rightP = 1; rightP < length; rightP++) {
            if (seen[s.charAt(rightP)] != -1 && seen[s.charAt(rightP)] >= leftP) {
                leftP = seen[s.charAt(rightP)] + 1;
                maxLength = Math.max(maxLength, rightP - leftP);
            } else {
                maxLength = Math.max(maxLength, rightP - leftP + 1);
            }

            seen[s.charAt(rightP)] = rightP;
        }

        return maxLength;
    }
}

---

Explanation of the Code:

1. Edge Case: We first handle the case where the input string is empty by returning 0.
2. Initialization:
   • We create an array seen of size 128 (to cover all ASCII characters), initialized with -1 to represent that no character has been seen yet.
   • We set the first character’s index in the seen array.
   • maxLength stores the length of the longest valid substring encountered so far.
   • leftP is the left pointer, which tracks the start of the current window.
3. Sliding Window Logic:
   • We iterate through the string with the rightP pointer.
   • If the character at rightP has been seen before (i.e., its last occurrence is within the current window), we move leftP to the right of the last occurrence to ensure no repeated characters are in the window.
   • Otherwise, we calculate the current valid substring length and update maxLength if it’s the longest we’ve found so far.
   • We update the seen array with the current index of the character at rightP.
4. Final Result: After completing the loop, maxLength holds the length of the longest substring without repeating characters.

Explanation with Example:

Let’s walk through the input s = "abcabcbb" step by step:

1. We start with both pointers at the beginning of the string (leftP = 0, rightP = 0).
2. We encounter ‘a’, ‘b’, and ‘c’ and add them to our sliding window, tracking their indices in seen. The longest valid substring is "abc", with a length of 3.
3. When we encounter the second ‘a’, we move leftP to the right of the first ‘a’ and continue.
4. The window then captures "bca", but the longest substring length remains 3.
5. Finally, the process continues until the last character, with the maximum length remaining 3.

Conclusion:

The sliding window technique allows us to efficiently track substrings without repetition, ensuring a time complexity of O(n) where n is the length of the input string. This solution is optimal for this problem and beats 91% of the other submissions in terms of runtime!

If you’re preparing for coding interviews, understanding and practicing this technique is a must. Don’t forget to check out the detailed video explanation on YouTube here.

Feel free to leave your questions or suggestions in the comments section below. Happy coding!