Java Program to Find Longest Substring Without Repeating Characters

Use a sliding window with a HashMap to track characters and their indices, updating the window start when repeats occur; in Java, this can be done with Map and two pointers to find the longest substring without repeating characters.

Examples

Inputabcabcbb

Output3

Inputbbbbb

Output1

Inputpwwkew

Output3

How to Think About It

To find the longest substring without repeating characters, imagine moving through the string with two markers that define a window. When you see a repeated character inside this window, move the start marker just past the previous occurrence of that character to keep all characters unique. Keep track of the longest window size found as you go.

Algorithm

1

Initialize a map to store characters and their latest indices.

2

Set two pointers: start and end, both at 0.

3

Move end pointer through the string characters.

4

If the character at end is already in the map and its index is >= start, move start to index + 1.

5

Update the character's index in the map to end.

6

Keep track of the maximum window size (end - start + 1).

7

Return the maximum window size after processing all characters.

Code

java

import java.util.HashMap;
import java.util.Map;

public class LongestSubstring {
    public static int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> map = new HashMap<>();
        int maxLen = 0, start = 0;
        for (int end = 0; end < s.length(); end++) {
            char c = s.charAt(end);
            if (map.containsKey(c) && map.get(c) >= start) {
                start = map.get(c) + 1;
            }
            map.put(c, end);
            maxLen = Math.max(maxLen, end - start + 1);
        }
        return maxLen;
    }

    public static void main(String[] args) {
        String input = "abcabcbb";
        System.out.println(lengthOfLongestSubstring(input));
    }
}

Dry Run

Let's trace the input "abcabcbb" through the code

1

Initialize variables

map = {}, maxLen = 0, start = 0

2

Process 'a' at index 0

map = {a:0}, maxLen = 1, start = 0

3

Process 'b' at index 1

map = {a:0, b:1}, maxLen = 2, start = 0

4

Process 'c' at index 2

map = {a:0, b:1, c:2}, maxLen = 3, start = 0

5

Process 'a' at index 3 (repeat)

start updated to 1 (map[a] + 1), map = {a:3, b:1, c:2}, maxLen = 3

6

Process 'b' at index 4 (repeat)

start updated to 2 (map[b] + 1), map = {a:3, b:4, c:2}, maxLen = 3

7

Process 'c' at index 5 (repeat)

start updated to 3 (map[c] + 1), map = {a:3, b:4, c:5}, maxLen = 3

8

Process 'b' at index 6 (repeat)

start updated to 5 (map[b] + 1), map = {a:3, b:6, c:5}, maxLen = 3

9

Process 'b' at index 7 (repeat)

start updated to 7 (map[b] + 1), map = {a:3, b:7, c:5}, maxLen = 3

Index	Character	Start	Map State	Max Length
0	a	0	{a=0}	1
1	b	0	{a=0, b=1}	2
2	c	0	{a=0, b=1, c=2}	3
3	a	1	{a=3, b=1, c=2}	3
4	b	2	{a=3, b=4, c=2}	3
5	c	3	{a=3, b=4, c=5}	3
6	b	5	{a=3, b=6, c=5}	3
7	b	7	{a=3, b=7, c=5}	3

Why This Works

Step 1: Tracking characters with a map

We use a map to remember the last index where each character appeared, so we know when a repeat happens.

Step 2: Sliding window with two pointers

Two pointers define the current substring window; when a repeat is found, we move the start pointer to keep characters unique.

Step 3: Updating maximum length

After each character, we calculate the current window size and update the maximum length if it's larger.

Alternative Approaches

Brute Force

java

public static int lengthOfLongestSubstringBruteForce(String s) {
    int maxLen = 0;
    for (int i = 0; i < s.length(); i++) {
        for (int j = i; j < s.length(); j++) {
            if (allUnique(s, i, j)) {
                maxLen = Math.max(maxLen, j - i + 1);
            }
        }
    }
    return maxLen;
}

private static boolean allUnique(String s, int start, int end) {
    boolean[] chars = new boolean[128];
    for (int i = start; i <= end; i++) {
        char c = s.charAt(i);
        if (chars[c]) return false;
        chars[c] = true;
    }
    return true;
}

Simple but slow; checks all substrings and is O(n^3) time.

Sliding Window with Set

java

import java.util.HashSet;
import java.util.Set;

public static int lengthOfLongestSubstringSet(String s) {
    Set<Character> set = new HashSet<>();
    int maxLen = 0, start = 0, end = 0;
    while (end < s.length()) {
        if (!set.contains(s.charAt(end))) {
            set.add(s.charAt(end));
            maxLen = Math.max(maxLen, set.size());
            end++;
        } else {
            set.remove(s.charAt(start));
            start++;
        }
    }
    return maxLen;
}

Uses a set to track characters; simpler but may be less efficient than map for index jumps.

Complexity: O(n) time, O(min(m, n)) space

Time Complexity

The algorithm visits each character once with the end pointer and moves the start pointer forward without going back, resulting in O(n) time.

Space Complexity

The map stores characters currently in the window, which can be at most the size of the character set or string length, so O(min(m, n)) where m is charset size.

Which Approach is Fastest?

The sliding window with a map is fastest due to direct index jumps; the set approach is simpler but may do more steps; brute force is slowest.

Approach	Time	Space	Best For
Sliding Window with Map	O(n)	O(min(m,n))	Efficient for all inputs
Sliding Window with Set	O(n)	O(min(m,n))	Simple implementation
Brute Force	O(n^3)	O(1)	Small inputs or learning