Longest Substring Without Repeating Characters in Java DSA: Sliding Window Made Simple

Solve Longest Substring Without Repeating Characters in Java DSA with a clear sliding window. Full step-by-step dry runs for brute force, HashSet, and index-array approaches.

1. Introduction

Longest Substring Without Repeating Characters in Java is a favourite interview question, and it is the problem that finally makes the sliding window idea click for most people. You get one string. You have to find the length of the longest stretch inside it where no letter repeats.

Let’s clarify one key point first: a substring is a sequence of characters that are right next to each other. For example, in the word “abcabcbb,” the parts “abc” and “bca” are substrings because they are made up of characters sitting right next to each other. However, “acb” isn’t a substring since its letters are not all consecutive.

The task asks for a length, not the substring itself. Take “abcabcbb”. The longest clean run is “abc”, which has 3 characters, so the answer is 3. The moment a fourth character repeats one already inside our run, the streak breaks.

We typically approach the problem in three friendly and practical steps. First, we consider checking every possible substring, which is the slowest method. Next, we speed things up using a sliding window with a HashSet. Finally, a more refined approach with an index lookup makes the solution leaner and is often appreciated by interviewers.

Every approach gets a full, step-by-step dry run on the same 8-character string. Nothing is skipped, so you can watch the two pointers move, see each character go in and out, and understand exactly why the window grows and shrinks.

2. Understanding the Problem

Let us pin down the rules before we touch any code.

• You get one string, for example s = “abcabcbb”.
• Return the length of the longest substring that has no repeated character.
• The characters in that substring must be next to each other, with no gaps.
• If the string is empty, the answer is 0, since there is nothing to measure.

For our string the answer is 3, coming from the run “abc” at the very start. After that, every new character bumps into a letter already in our current run, so the window can never grow past 3.

Keep one thing in mind throughout. We only ever care about the longest length we have seen, so we save that best value and keep updating it as we scan.

3. Concepts You Need Here

3.1 A Window Is Just Two Pointers

A sliding window is a stretch of the string marked by two pointers. We call them lower and higher. The lower pointer marks where our current run starts, while the higher pointer marks where it ends.

• The higher pointer moves forward one step at a time to pull in new characters.
• Our lower pointer only moves forward when we hit a repeat and need to shrink.

So the window is the slice from lower to higher, and its length is higher minus lower plus one.

3.2 We Need a Fast Way to Spot Repeats

As the window expands, we need to quickly verify if a new character is already within it. Scanning the entire window each time would be inefficient, so we maintain a separate record of its current contents.

• A HashSet tracks which characters are currently in the window.
• An index array remembers the last position where each character was seen, which lets the lower pointer jump instead of crawl.

4. Approach 1: Check Every Substring

The main idea is to examine each substring for repeats. Start with a position, then extend the end outward. For every extension, verify if all characters are unique. Keep track of the longest one that’s all clean. It works well, but it involves quite a bit of repeated checking.

4.1 Pseudocode

best = 0
 
for start in 0 .. length(s) - 1:
    seen = empty set
    for end in start .. length(s) - 1:
        ch = s[end]
        if ch is already in seen:
            break        // repeat found, stop this start
        add ch to seen
        windowLen = end - start + 1
        best = max(best, windowLen)
 
return best

4.2 Pseudocode Explained

The whole idea rests on one plain thought. Any character in the string could be the first letter of the best clean run, so we simply try every character as a starting point and see how far each one reaches. Let us walk the pseudocode part by part.

Set up the best tracker. The line best = 0 serves as a starting point for tracking the longest clean run throughout the process. We intentionally keep it outside both loops, so it can remember the largest run found across all starting points we test. Beginning it at 0 is a safe choice because any actual run we discover will be at least 1, which will then update this value.

Fix a starting point. The outer loop, for start in 0 .. length(s) – 1, walks the start pointer across every index in the string. Each pass picks one fixed starting position and asks a simple question: beginning here, how long can a run go before a letter repeats? We must try all starts because the best run could begin anywhere, not just at index 0.

Reset the memory for this start. Inside the outer loop, ‘seen = empty set’ clears the record at the beginning of each new start. This reset is very important because each start is a fresh attempt, and we want to make sure characters from previous starts don’t carry over. If they did, the repeat check could give us false results.

Stretch the end outward. The inner loop, for end in start .. length(s) – 1, grows a second pointer forward from the current start. So the pair start and end mark the slice we are testing right now. As end moves right, the slice gets longer one character at a time.

Read and test the new character. The line ch = s[end] grabs the character sitting at the end pointer. Then the check whether ch is already in seen asks whether this exact character has appeared earlier in the current slice. If the answer is yes, the run cannot continue because repeats aren’t allowed, so break stops this inner loop and returns control to the outer loop to start again.

Record and measure. When the character is fresh, add ch to seen writes it into the record so future steps in this same slice will spot it if it repeats. Next, windowLen = end – start + 1 measures how many characters the clean slice now holds. The plus one is there because both ends are included: a slice from index 2 to index 4 covers 2, 3, and 4, which is three characters.

Keep the largest length. Finally, best = max(best, windowLen) compares the current slice length with the best we’ve seen and keeps the larger one. So even if a later start finds a shorter run, best never shrinks. After all starts finish, return best hands back the single largest clean length found in the whole string.

4.3 Java Code

import java.util.*;
 
public class LongestSubstringBrute {
 
    public static int lengthOfLongestSubstring(String s) {
        int best = 0;
        for (int start = 0; start < s.length(); start++) {
            Set<Character> seen = new HashSet<>();
            for (int end = start; end < s.length(); end++) {
                char ch = s.charAt(end);
                if (seen.contains(ch)) {
                    break;
                }
                seen.add(ch);
                best = Math.max(best, end - start + 1);
            }
        }
        return best;
    }
 
    public static void main(String[] args) {
        System.out.println(lengthOfLongestSubstring("abcabcbb")); // 3
    }
}

4.4 Java Code Explained

This is the same plan in Java. A fresh HashSet is used for each start, so old characters never leak into a new run.

• Line 6 sets best to 0, since we have not measured any run yet.
• Line 7 starts the outer loop that fixes each start position in turn.
• On line 8 a new empty set is created for the current start, holding only this run’s characters.
• Line 9 grows the end pointer forward from start to the end of the string.
• Then line 11 checks the set. If the character is already there, line 12 breaks and we abandon this start.
• Line 14 adds the fresh character, and line 15 updates best with the current window length.

4.5 Dry Run of the Brute Force

Let us trace s = “abcabcbb”, which has 8 characters at indices 0 to 7. To keep the table short, we show each start and how far its inner loop reaches before a repeat stops it.

Every start peaks at 3 or less, so best stays at 3 the whole way. The method returns 3.

4.6 Reading the Dry Run

Let us walk every start one by one and see exactly why each run stops where it does. Remember the string is s = “abcabcbb” with indices 0 to 7.

Start = 0, the run abc. We begin at index 0 with an empty set.

• At end=0 we read a. It is new, so the set becomes {a}, the length is 1, and best becomes 1.
• Moving to end=1 we read b. Still new, so the set is {a, b}, the length is 2, and best becomes 2.
• Reading end=2 gives c. Again new, so the set is {a, b, c}, the length is 3, and best becomes 3.
• At end=3 we read a. This letter is already in the set, so the run is spoiled and we break.

So this start reaches a clean run of 3, the substring “abc”. Best is now 3.

Start = 1, the run bca. The outer loop moves the start to index 1, and the set is wiped clean again.

• At end=1 we read b, which is new, so the set is {b} and the length is 1.
• Reading end=2 gives c, new again, so the set is {b, c} and the length is 2.
• At end=3 we read a, still new, so the set is {b, c, a} and the length climbs to 3.
• Moving to end=4 we read b, which already sits in the set, so we break.

This start also tops out at 3, the substring “bca”. Best is already 3, so it does not change.

Start = 2, the run cab. Now the start moves to index 2 with a fresh empty set.

• At end=2 we read c, new, so the set is {c} and the length is 1.
• Reading end=3 gives a, new, so the set is {c, a} and the length is 2.
• At end=4 we read b, still new, so the set is {c, a, b} and the length reaches 3.
• Moving to end=5 we read c, which is already in the set, so we break.

Another run of 3, the substring “cab”. Best holds at 3.

Start = 3, the run abc again. The start is now index 3, and the set resets once more.

• At end=3 we read a, new, so the set is {a} and the length is 1.
• Reading end=4 gives b, new, so the set is {a, b} and the length is 2.
• At end=5 we read c, still new, so the set is {a, b, c} and the length hits 3.
• Moving to end=6 we read b, already in the set, so we break.

Yet another run of 3, the substring “abc”. Best stays at 3.

Start = 4 onward, the short tails. From index 4 the leftover string is just b, c, b, b, which is crowded with repeats, so these starts run out of room quickly.

• Start 4 reads b at end=4 then c at end=5, but end=6 brings another b, so it breaks at length 2.
• From start 5 we read c at end=5 then b at end=6, and the b at end=7 breaks it at length 2.
• Then start 6 reads b at end=6, and the b at end=7 breaks it right away at length 1.
• Finally start 7 reads the last b at end=7 and the string simply ends, giving length 1.

None of these tail starts can reach 3, so best finishes at 3 and the method returns 3. Notice the real cost of this approach. We rebuilt the set from scratch for every single start and re-read characters we had already checked many times over. The sliding window fixes exactly this waste.

4.7 Time and Space Cost

• Time is O(n²), because each start can scan most of the string again.
• Space is O(k), where k is the number of distinct characters held in the set.

The repeated scanning is the problem. Next we let one window slide across the string just once, so no character gets re-read from scratch.

5. Approach 2: Sliding Window With a HashSet

Keep one window open and slide it smoothly. The higher pointer brings in a new character with each step. If that character’s already inside the window, we gently move the lower pointer forward, dropping characters until the repeat is gone. After each safe addition, we measure the window size and update the best. Each character enters and leaves the set at most once, so the entire scan remains efficient and straightforward.

5.1 Pseudocode

window = empty set
lower = 0
best = 0
 
for higher in 0 .. length(s) - 1:
    ch = s[higher]
    while ch is in window:
        remove s[lower] from window   // shrink from the left
        lower = lower + 1
    add ch to window                  // now safe to add
    windowLen = higher - lower + 1
    best = max(best, windowLen)
 
return best

5.2 Pseudocode Explained

The major improvement from brute force is that we no longer start from scratch each time. Instead of rebuilding a run every time we begin anew, we maintain a single window and slide it across the string just once. This window can expand to the right and contract on the left, but it always moves forward. Let’s go through it line by line.

Set up the window and its trackers. The line window = empty set holds the characters that sit inside the current window right now, and nothing else. Then lower = 0 marks the left edge of the window, and best = 0 remembers the longest clean run so far. These three lines live outside the loop because they must survive across every step of the scan.

Drive the right edge forward. The loop that runs from 0 to length(s) – 1 gently moves the higher pointer through the string, one step at a time. Imagine higher as the edge that brings new characters into the window, steadily progressing forward. Since it only moves forward, each character is read just once during this loop.

Look at the incoming character. The line ch = s[higher] grabs the character the right edge is about to bring in. Before we can safely add it, we must make sure it does not already sit inside the window, because the window is supposed to hold only unique characters.

Shrink from the left while there is a clash. This is the heart of the approach. The line while ch is in window keeps looping as long as the incoming character already exists in the window. Inside, remove s[lower] from window drops the character at the left edge out of the set, and lower = lower + 1 slides the left edge one step to the right. So we keep peeling characters off the left until the duplicate copy of ch is gone. We use a while, not an if, because in some cases more than one removal is needed before the clash clears.

Add the character safely. Once the while loop ends, the window no longer contains ch, so adding ch to window incorporates the new character into the set. Now, the window is clean again, stretching from lower to higher without any repeats.

Measure and save the best. The line windowLen = higher – lower + 1 counts how many characters the clean window now holds, with the plus one again because both edges are included. Then best = max(best, windowLen) keeps the larger of the current window and the best seen before, so best only ever grows. After the whole string is scanned, return best gives the final answer. Because each character is added once and removed at most once, the entire scan stays fast.

5.3 Java Code

import java.util.*;
 
public class LongestSubstringSet {
 
    public static int lengthOfLongestSubstring(String s) {
        Set<Character> window = new HashSet<>();
        int lower = 0;
        int best = 0;
        for (int higher = 0; higher < s.length(); higher++) {
            char ch = s.charAt(higher);
            while (window.contains(ch)) {
                window.remove(s.charAt(lower));
                lower++;
            }
            window.add(ch);
            best = Math.max(best, higher - lower + 1);
        }
        return best;
    }
 
    public static void main(String[] args) {
        System.out.println(lengthOfLongestSubstring("abcabcbb")); // 3
    }
}

5.4 Java Code Explained

The Java code follows the window idea directly. One set holds only the characters currently between lower and higher.

• Line 6 creates the set that mirrors the window’s contents.
• Lines 7 and 8 set lower to 0 and best to 0 before the scan starts.
• Line 9 drives the higher pointer forward across the whole string.
• Then line 11 runs a while loop that shrinks from the left while the new character is a duplicate.
• Inside, line 12 removes the leftmost character and line 13 advances lower.
• Line 15 adds the now-safe character, and line 16 updates best with the current window length.

5.5 Dry Run of the Sliding Window

Let’s carefully go through s = “abcabcbb” again, from indices 0 to 7. Each step shows one action. When we see a shrink row, it means we’re removing a character from the left. An add row indicates we’re adding a new character into the window.

Legend: higher is the read pointer, lower is the left edge, window shows the set after the action, best is the largest length so far.

The window never grows past 3, so best finishes at 3. The method returns 3.

5.6 Reading the Dry Run

Let us go step by step and watch the window breathe in and out.

Steps higher=0 to 2, the window fills up. These first three characters are all different, so nothing needs shrinking.

• At higher=0 we add a, the window is {a}, and best becomes 1.
• Reading higher=1 adds b, the window is {a, b}, and best climbs to 2.
• By higher=2 we add c, the window is {a, b, c}, and best reaches 3.

So far, lower hasn’t changed at all. The window covers the entire slice from index 0 to index 2, and index 3 is where we find our first real answer.

Step higher=3, the first repeat. Now we read a, but a is already in the window {a, b, c}.

• The while loop fires, so we remove the leftmost character s[0] which is a, and push lower to 1.
• Now the window is {b, c} and the repeat is gone, so the loop stops.
• We add the new a, giving {b, c, a}, and the window length is 3 minus 1 plus 1, which is 3.

Best stays at 3 because the window is the same size, just shifted one step to the right.

Steps higher=4 and higher=5, the same dance. Each new character collides with an old copy, so each time we drop one from the left and slide across.

• At higher=4 the b repeats, so we remove s[1] which is b, lower becomes 2, then we add b to get {c, a, b}, length 3.
• At higher=5 the c repeats, so we remove s[2] which is c, lower becomes 3, then we add c to get {a, b, c}, length 3.

As these steps unfold, the window stays at a size of 3 and gently progresses to the right. Best remains steady and confident throughout.

Step higher=6, a double shrink. Here we read b, and this time the window {a, b, c} needs two removals before b is clear.

• First we remove s[3] which is a, so lower becomes 4 and the window is {b, c}.
• The letter b is still inside, so we remove s[4] which is b, lower becomes 5, and the window is {c}.
• Now b is gone, so we add it to get {c, b}, and the window length is only 2.

This is the first time the window has actually shrunk below 3. Luckily, the ‘best’ doesn’t change though, since it only keeps track of the largest length we’ve seen, which remains at 3.

Step higher=7, the window empties then refills. The last character is another b, and it clashes with the b already in {c, b}.

• We remove s[5] which is c, lower becomes 6, and the window is {b}.
• The b is still there, so we remove s[6] which is b, lower becomes 7, and the window is empty.
• Finally we add b, the window is {b}, and the length is just 1.

The scan is done. The best was set to 3 early on, and nothing ever beat it, so the method returns 3. Notice that every character was added once and removed at most once, which is why one pass is enough.

5.7 Time and Space Cost

• Time is O(n), since each character enters and leaves the window at most once.
• Space is O(k), where k is the number of distinct characters that can appear.

This approach is a big step up from brute force. However, the shrink loop might feel a bit slow when many repeats build up, as it removes characters one at a time. Luckily, using an index lookup allows the lower pointer to skip right past the repeat in a single, efficient move.

6. Approach 3: Sliding Window With an Index Lookup

Instead of maintaining a set, track the last position where each character appeared. When the upper pointer encounters a character it has seen before, and that previous position is within the current window, move the lower pointer directly to just after that position. This eliminates the slow shrinking loop, replacing it with a single, efficient jump. For ASCII input, a simple int array of size 128 suffices to store these positions.

6.1 Pseudocode

last = array of 128 values, all set to -1
lower = 0
best = 0
 
for higher in 0 .. length(s) - 1:
    ch = s[higher]
    if last[ch] >= lower:
        lower = last[ch] + 1     // jump past the old copy
    last[ch] = higher            // record newest position
    windowLen = higher - lower + 1
    best = max(best, windowLen)
 
return best

The HashSet version was fast, but its shrink loop could remove characters one at a time, which feels wasteful. This version fixes that by remembering more. Instead of just knowing which characters are in the window, we remember the last index where each character appeared. That extra memory lets the left edge leap straight to the right spot in a single move. Let us read it line by line.

Set up the memory array. The line last = array of 128 values, all set to -1 makes one slot for every ASCII character. Each slot will hold the most recent index where that character was seen. We fill every slot with -1 at the start, and -1 is a deliberate signal meaning we have not seen this character yet. That default matters, as you will see in the jump check.

Set up the window trackers. Just like before, when lower = 0, it marks the left edge of the window, and best = 0 keeps track of the longest clean run. There’s no need to set anything this time because the last array takes care of all the remembering for us.

Drive the right edge forward. The loop for higher in 0 .. length(s) – 1 moves the higher pointer across the string, reading one character per step. The line ch = s[higher] grabs the current character so we can look up its history.

Decide whether to jump the left edge. This is the clever part. The check if last[ch] >= lower asks whether the last time we saw this character falls at or after the current left edge. If it does, that earlier copy is still inside the window, so the window is no longer clean. To fix it in one move, lower = last[ch] + 1 slides the left edge to just past that old copy. We compare against lower for a reason: if last[ch] is smaller than lower, the old copy already fell out of the window earlier, so we must ignore it and leave lower where it is. Skipping this check would let lower jump backward, which would break everything.

Record the newest position. The line last[ch] = higher overwrites the character’s slot with its current index. This way, the array always knows the most recent position where the character resides. Updating this at every step helps keep the memory current and accurate.

Measure and save the best. Finally windowLen = higher – lower + 1 counts the clean window, and best = max(best, windowLen) keeps the larger value. After the scan, return best gives the answer. Notice there is no inner loop at all, so each character is touched exactly once, which is why this version is the leanest of the three.

6.3 Java Code

import java.util.*;
 
public class LongestSubstringIndex {
 
    public static int lengthOfLongestSubstring(String s) {
        int[] last = new int[128];
        Arrays.fill(last, -1);
        int lower = 0;
        int best = 0;
        for (int higher = 0; higher < s.length(); higher++) {
            char ch = s.charAt(higher);
            if (last[ch] >= lower) {
                lower = last[ch] + 1;
            }
            last[ch] = higher;
            best = Math.max(best, higher - lower + 1);
        }
        return best;
    }
 
    public static void main(String[] args) {
        System.out.println(lengthOfLongestSubstring("abcabcbb")); // 3
    }
}

6.4 Java Code Explained

The code is short because the array does the remembering. One pass, no inner loop.

• Line 6 makes an int array of 128 slots, one for each ASCII character.
• Line 7 fills every slot with -1, marking all characters as never seen.
• Lines 8 and 9 set lower and best to 0 before the scan.
• Line 10 moves the higher pointer across the string one character at a time.
• Then line 12 checks if this character’s last position is inside the window, and line 13 jumps lower past it.
• Line 15 records the newest position, and line 16 updates best with the current length.

6.5 Dry Run of the Index Lookup

Let’s go through s = “abcabcbb” once more together. Each row represents a step with a higher pointer. The jump column indicates if the lower pointer moved during that step, and last[ch] shows the position we just recorded.

Legend: higher is the read pointer, char is s[higher], last[char] is the stored index for that letter, lower is the left edge after any jump, len is higher minus lower plus one.

Best hits 3 at higher=2 and stays there. The method returns 3.

6.6 Reading the Dry Run

Let us step through and watch the lower pointer jump instead of crawl.

Steps higher=0 to 2, no jumps needed. The first three characters are brand new, so their old positions are all -1.

• At higher=0 we store last[a] = 0. Since -1 was below lower, no jump happens, and length is 1.
• Reading higher=1 stores last[b] = 1, no jump, and length becomes 2.
• By higher=2 we store last[c] = 2, still no jump, and length reaches 3.

Lower is still 0 here, and best has climbed to 3 with the run “abc”.

Step higher=3, the first jump. Now we read a, and last[a] is 0.

• Because 0 is greater than or equal to lower (which is 0), the old a sits inside the window.
• So lower jumps to last[a] plus 1, which is 1, skipping straight past the old a.
• We then store last[a] = 3, and the length is 3 minus 1 plus 1, which is 3.

Notice the win here. The HashSet version needed a removal step to shrink, but the array jumped the left edge in one move.

Steps higher=4 and higher=5, more single jumps. Each character repeats exactly once inside the window, so lower jumps one slot each time.

• At higher=4 the letter b has last[b] = 1, which is inside, so lower jumps to 2 and we store last[b] = 4.
• At higher=5 the letter c has last[c] = 2, which is inside, so lower jumps to 3 and we store last[c] = 5.

Through both steps the window length stays at 3, so best holds at 3 while the window glides right.

Step higher=6, a bigger jump. We read b, and last[b] is now 4.

• Since 4 is at or after lower (which is 3), the old b is inside the window.
• So lower jumps to 4 plus 1, which is 5, skipping two characters at once.
• We store last[b] = 6, and the length is 6 minus 5 plus 1, which is 2.

This single jump did the work that took the HashSet two separate removals. The window is now smaller, but best still remembers 3.

Step higher=7, the final jump. The last character is b again, and last[b] is 6.

• Because 6 is at or after lower (which is 5), the old b is still in the window.
• So lower jumps to 6 plus 1, which is 7, and we store last[b] = 7.
• The length is 7 minus 7 plus 1, which is 1, the smallest window of all.

The scan ends. Best was locked at 3 early and never beaten, so the method returns 3. The array version reached the same answer with no inner loop at all.

6.7 Comparing the Three Traces

7. Comparing the Three Approaches

All three return the same answer of 3. They just pay different prices to get there.

Both window versions operate over the same linear time, but they have a key difference in the shrink step. The HashSet gently moves the left edge forward, whereas the index array takes a big leap in a single jump, all while using just a small, fixed amount of memory.

During the interview, start by mentioning brute force to acknowledge the straightforward approach. Then, introduce the HashSet as a simple fix and highlight the index array as your top choice. Keep the HashSet as a reliable backup for inputs that extend beyond basic ASCII characters.

8. Common Mistakes and Edge Cases

A few small traps catch beginners on this problem. Keep them in mind.

• Forgetting to compare last[ch] with lower lets the left pointer jump backward, which breaks the window.
• Returning the substring instead of its length, when the question only asks for the length.
• Remember, resetting best inside the loop will clear out the largest value you’ve already found, so be sure to handle it carefully.
• Assuming only lowercase letters, when the input may include digits, spaces, or symbols.
• An empty string should return 0, so make sure the loop simply never runs and best stays 0.

Run an empty string and a single-character string through your code before you call it done. Small inputs like these catch more bugs than any long input will.

9. Interview Questions

10. Conclusion

Understanding the Longest Substring Without Repeating Characters in Java might seem challenging at first, but it actually highlights a key pattern you’ll find yourself using often: the sliding window. Once you start seeing the string as a window that expands on the right and contracts on the left, everything begins to click and feels much more approachable.

Our 8-character trace showed the payoff clearly. Brute force re-checked the same characters over and over. The HashSet window slid across in one pass, dropping the left edge when a repeat appeared. The index array did the same thing but jumped the left edge instantly.

Focus on understanding the pattern, not just the answer. When faced with a problem asking for the longest or shortest run that follows a certain rule, try using two pointers and a sliding window. Keep a set or an index map handy to catch issues quickly. This way, many challenging string problems become much easier and more manageable.

11. Further Reading

• LeetCode Longest Substring Without Repeating Characters — practice the original problem and submit your own solution.
• Oracle Java HashSet documentation — the official reference for the set used in approach two.
• Previous in this series: Sliding Window Maximum Average Subarray in Java DSA
• Next in this series: Minimum Size Subarray Sum in Java — shrink a window to find the shortest run that reaches a target sum.