Longest Substring Without Repeating Characters LeetCode Solution

Given a string, find the length of the longest substring without repeating characters.

Example:

Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Understand The Problem

The first step in problem-solving is to understand the problem.

When you read the problem statement, you might immediately have ideas on how to solve it. Do not jump to conclusions and do not let your mind fool you. It’s best not to trust your instincts, and instead, you should go through systematic steps of analyzing the problem. Using a system will dramatically reduce the chance of a mistake.

Note: During the interview, make sure to ask questions before you start solving the problem! Interviewers often give a vague problem definition, and you have to fill in the details by asking questions.

Let’s look at the problem statement:

• Given a string, find the length of the longest substring without repeating characters.

There is a lot to unpack in every problem statement. First, let’s look at the question overall and then highlight the key parts:

• We are given a string.
• We need to find the length of the longest substring without repeating characters.

From this information, we can form a basic idea of how the function will look like:

public class LongestSubstring {
    public int lengthOfLongestSubstring(String s) {
        // Your code here
    }
}

At this point, we have no idea how to solve anything. However, we do know the input, we do know the output, and we have a basic sense of the algorithm. Let’s dive a little more into the details before we try coming up with a solution…

Let’s analyze the input.

• String (s):
  • Could the string be empty?
    • Yes.
  • Can we expect the string to contain only ASCII characters?
    • Yes.
  • Could the string contain spaces or special characters?
    • Yes.
  • Could the string contain uppercase and lowercase letters?
    • Yes.

Note: Notice how simple these questions are. Yet they are so crucial. ANY change in the answers can mean the difference between solving the algorithm and getting it wrong.

We now have a basic understanding of the problem. Let’s try to come up with a solution.

Note: There’s always a chance you miss something – even after carefully examining each detail. Don’t worry. It’s natural. However, you should treat every mistake as an opportunity to improve. Why did you make a mistake? Can you improve your problem-solving system to ensure that you don’t make the same mistake again? That’s the whole point of learning: identify weaknesses, improve your system, and repeat. Iterate, iterate, iterate.

Coming Up With The Solution

Each algorithm problem is different. There is no single approach that will help you solve every problem. However, I recommend starting by creating examples and walking through them.

Let’s start by creating examples:

• Example 1
  • s = "abcabcbb"
  • Why this example?
    • This input is nice because it’s simple.
    • It tests the scenario where the longest substring is at the beginning of the string.
• Example 2
  • s = "bbbbb"
  • Why this example?
    • This input is nice because it tests the scenario where all characters in the string are the same.
    • It tests the scenario where the longest substring is the entire string.
• Example 3
  • s = "pwwkew"
  • Why this example?
    • This input is nice because it tests the scenario where the longest substring is in the middle of the string.
    • It tests the scenario where the substring has repeating characters but the longest substring does not.

Note: The number of examples you can go through during the interview will be limited. If you have infinite time, it’s best to try a lot of examples where each examines a specific edge-case. However, you don’t have infinite time in an interview, so you have to strike the balance between speed and accuracy.

As a result of not having a lot of time, let’s pick an example that seems to cover various edge-cases:

• s = "abcabcbb"

This example is nice because:

• It’s a simple case with a repeating substring.
• It involves finding the longest substring without repeating characters.
• The result is not the entire string, so we can test the correctness of the algorithm.

Exercise:

With the observations in mind, let’s take the example s = "abcabcbb" and start thinking about how we can find the length of the longest substring without repeating characters:

• We need to use a sliding window approach:
  • We’ll use two pointers to represent the start and end of the current substring.
  • We’ll initialize the start pointer at index 0 and the end pointer at index 0.
  • We’ll move the end pointer to the right until we encounter a repeating character.
  • We’ll update the length of the longest substring if the current substring is longer.
  • We’ll move the start pointer to the right until we remove the repeating character from the current substring.
  • We’ll repeat this process until the end pointer reaches the end of the string.

Example Dry Run:

• Let’s say our string is "abcabcbb".
• We’ll use two pointers to represent the start and end of the current substring.
• We’ll initialize the start pointer at index 0 and the end pointer at index 0.
• At each step, we’ll move the end pointer to the right until we encounter a repeating character.
  • At index 3, we encounter the repeating character 'a'.
  • The current substring is "abc".
  • We update the length of the longest substring to 3.
  • We move the start pointer to the right until we remove the repeating character 'a'.
  • The current substring becomes "bc".
  • We continue this process until the end pointer reaches the end of the string.
• The length of the longest substring without repeating characters is 3.

From this exercise, we have derived an algorithm:

• Initialize two pointers to represent the start and end of the current substring.
• Initialize the start pointer and end pointer to index 0.
• Move the end pointer to the right until we encounter a repeating character.
• Update the length of the longest substring if the current substring is longer.
• Move the start pointer to the right until we remove the repeating character from the current substring.
• Repeat this process until the end pointer reaches the end of the string.

Here is the algorithm written down:

public class LongestSubstring {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        Set<Character> set = new HashSet<>();
        int longestSubstringLength = 0, i = 0, j = 0;

        while (i < n && j < n) {


            if (!set.contains(s.charAt(j))) {
                set.add(s.charAt(j++));
                longestSubstringLength = Math.max(longestSubstringLength, j - i);
            } else {
                set.remove(s.charAt(i++));
            }
        }

        return longestSubstringLength;
    }
}

Note:This process may sound simplistic to you, but there is a powerful lesson here. You can make a simple observation like “We need to use a sliding window approach,” and begin by doing the most straightforward thing possible: initializing two pointers to represent the start and end of the current substring. Then, let the algorithm evolve from there.

If you are familiar with strings and hashmaps, you can see that the algorithm can be solved in O(N). From this information, we can make further observations:

• To do better, we can solve this in:
  • O(N) or O(N^2)
  • Not all algorithms fit neatly into these time-complexity buckets, but a lot of them do – especially in interviews. As a result, making this type of analysis is helpful to keep moving toward a solution.

Let’s consider each time-complexity and create more insights:

• O(N) algorithm means we need to traverse the string once.
  • We can use a hashmap to store the characters and their indices.
  • Additional space complexity might be required if we create a substring to store the result.
• O(N^2) algorithm means we might need nested loops or brute-force techniques.
  • This could involve checking every possible substring for duplicates.

Note: Notice how we can utilize prior knowledge of time-complexity, algorithms, and data structures to generate ideas of how to solve the problem. Make sure to study the Terminology!

Let’s use the O(N) observation. We have a string and need to find the longest substring without repeating characters.

When we consider finding the longest substring without repeating characters in the string:

s: "abcabcbb"

The longest substring without repeating characters is “abc”, with a length of 3.

Cool. We found the longest substring, but what does that give us?

We formed a new property for the input: the ability to traverse the string. Can we somehow exploit this property?

• Let’s begin by repeating what we did above: start from the beginning of the string.
  • Traverse the string while keeping track of the characters and their indices.
  • Use a hashmap to store the characters and their last seen indices.
• While we found the longest substring, we did find a pattern:
  • We can use a sliding window approach to track the current substring without repeating characters.
  • We need to update the start index of the window when a repeating character is encountered.
• Let’s clarify some of the things we are noticing:
  • The length of the current substring without repeating characters is the difference between the current index and the start index of the window.
  • We need to update the start index of the window when a repeating character is encountered to ensure that the substring remains valid.

Let’s recap:

1. By traversing the string, we found a pattern for finding the longest substring without repeating characters.
2. Then, by analyzing the pattern, we realized that we need to use a sliding window approach to track the current substring.

Note: Leaping to this conclusion is not always straightforward. However, with a lot of practice, and by using the “start from the beginning” tactic, you will be able to find these types of insights.

These observations give us an O(N) algorithm:

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        int maxLength = 0;
        Map<Character, Integer> charIndexMap = new HashMap<>();

        for (int start = 0, end = 0; end < n; end++) {
            char currentChar = s.charAt(end);
            if (charIndexMap.containsKey(currentChar)) {
                start = Math.max(charIndexMap.get(currentChar) + 1, start);
            }
            maxLength = Math.max(maxLength, end - start + 1);
            charIndexMap.put(currentChar, end);
        }

        return maxLength;
    }
}

Algorithm Analysis:

• Time Complexity: The algorithm traverses the string once, so the time complexity is O(N), where N is the length of the input string.
• Space Complexity: The algorithm uses a hashmap to store characters and their indices, so the space complexity is O(min(N, M)), where M is the size of the character set.

Dry Run:

Let’s dry run the algorithm with an example:

s: "abcabcbb"

1. Start from the beginning of the string: “a”.
2. Traverse the string while updating the hashmap with characters and their last seen indices.
3. When a repeating character “b” is encountered, update the start index of the window to the next character after the last occurrence of “b”.
4. Keep track of the maximum length of the current substring without repeating characters.
5. Continue until the end of the string is reached.
6. Return the maximum length of the substring without repeating characters.

Testing / Reflection

During an interview, if you have the time, you want to test your code by walking through it step-by-step. It’s not uncommon to make a silly mistake.

During practice, you want to reflect on how the solving process went by asking various questions:

• What is the time complexity?
  • O(N)
• What is the space complexity?
  • O(min(N, M))
• What are some interesting observations from this problem?
  • The algorithm involves traversing the string and using a sliding window approach to find the longest substring without repeating characters.
  • We need to update the start index of the window efficiently when a repeating character is encountered.
• What are some related problems?
  • There are other variations of this problem like finding the first substring without repeating characters.

Reflection is a great step that allows us to “chunk” the learnings from the problem by connecting it to existing ideas.

What else can you think of? Send feedback!

P.S. you can try it @ https://leetcode.com/problems/longest-substring-without-repeating-characters/