LeetCode #3: Longest Substring Without Repeating Characters — Solved in Java

Basic Sliding Window and Interview-Optimized Version

Image Source

This is one of those early medium difficulty LeetCode problems that shows up often and takes a bit of thinking to get right. You’re given a string and need to figure out the longest substring without repeating any characters. The twist is that the substring has to be contiguous, and you're not allowed to shuffle or skip. It’s all about finding where the repeats are and managing what you’ve already seen.

It’s a good intro to the sliding window pattern, but you don’t need to know the name to write the solution. You just need a way to keep track of characters you've already checked while moving through the string. We’ll go through each solution step by step to show exactly how it works.

LeetCode: Longest Substring Without Repeating Characters

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

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.

Constraints:

• 0 <= s.length <= 5 * 104

• s consists of English letters, digits, symbols and spaces.

Solution 1 — Basic Sliding Window (O(n))

Java Sliding Window Solution for Longest Substring

This solution moves through the string one character at a time and tracks the longest stretch without repeats. It uses a map to remember the last place each character appeared and two pointers to keep the current substring valid as we move forward.

Let’s walk through it:

class Solution {

This defines the class for your solution. It follows LeetCode’s expected structure.

public int lengthOfLongestSubstring(String s) {

The method takes a string and returns the length of the longest substring without repeated characters.

Map<Character, Integer> seen = new HashMap<>();
int start = 0;
int max = 0;

We start with an empty map to keep track of characters we’ve already seen and their latest positions. The start pointer marks the beginning of the current valid substring. The max variable keeps track of the best result we've found so far.

for (int end = 0; end < s.length(); end++) {
char c = s.charAt(end);

This loop moves the end pointer across the string, one character at a time. The variable c holds the current character.

if (seen.containsKey(c)) {
start = Math.max(seen.get(c) + 1, start);
}

If we’ve seen the current character before and it’s still inside our current window, we move start past that character’s previous position. The Math.max is used to make sure we don’t accidentally move start backward if the repeated character is already outside the window.

seen.put(c, end);

We update the map to store the new position of the current character. This replaces whatever older position it had.

max = Math.max(max, end - start + 1);

Here we check if the current window is the longest one so far. If it is, we update max.

}

This closes the loop that walks across the string.

return max;
}

For the final step, we return the longest length we found with no repeating characters.

This only passes through the string once, so it runs in O(n) time. Every character is checked and updated just one time. Memory use depends on how many different characters show up, which means space is O(min(n, Σ)), where Σ is the size of the character set. For standard ASCII, that's a small constant.

Solution 2 — Interview-Optimized Version (O(n))

Java Interview Solution for Longest Substring

This version works just like the basic one but trims things down a bit. It’s easier to explain out loud and fits well in a whiteboard or interview setting. The logic is the same, just with cleaner variable names and a more direct flow.

Let’s walk through it:

class Solution {

This is the start of the class. LeetCode provides this part for you.

public int lengthOfLongestSubstring(String s) {

We define a method that takes in a string and returns the length of the longest substring without repeated characters.

int left = 0;
int maxLen = 0;
Map<Character, Integer> map = new HashMap<>();

We use left to track the start of the current window. maxLen will store the best length we’ve found so far. The map keeps track of each character’s most recent index.

for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);

We move right across the string one character at a time. The variable c is the character at the current position.

if (map.containsKey(c)) {
left = Math.max(map.get(c) + 1, left);
}

If this character has been seen before, and the last time we saw it is still inside the current window, we move left just after its previous index. We use Math.max to make sure we don’t accidentally move left backward if the repeat is already behind us.

map.put(c, right);

We update the map to store the current position of this character. That way, future repeats will know where to start fresh from.

maxLen = Math.max(maxLen, right - left + 1);

We check if the current window is the longest one so far. If it is, we store the length in maxLen.

}

This closes the loop that walks through the string.

return maxLen;
}

After the loop finishes, we return the longest length we found without repeats.

This method runs in O(n) time because each character is visited once. The space usage depends on how many unique characters show up, so it's O(min(n, size of the character set)). It's a great pattern to show in interviews because it’s efficient, easy to reason about, and doesn’t require any fancy helper methods or extra logic.

Basic Sliding Window — Copy and Paste

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> seen = new HashMap<>();
        int start = 0;
        int max = 0;

        for (int end = 0; end < s.length(); end++) {
            char c = s.charAt(end);

            if (seen.containsKey(c)) {
                start = Math.max(seen.get(c) + 1, start);
            }

            seen.put(c, end);
            max = Math.max(max, end - start + 1);
        }

        return max;
    }
}

Interview Version — Copy and Paste

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int left = 0;
        int maxLen = 0;
        Map<Character, Integer> map = new HashMap<>();

        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);

            if (map.containsKey(c)) {
                left = Math.max(map.get(c) + 1, left);
            }

            map.put(c, right);
            maxLen = Math.max(maxLen, right - left + 1);
        }

        return maxLen;
    }
}