Longest Substring Without Repeating Characters In Java

Longest Substring Without Repeating Characters

When we given a String (s), it should find the length of the longest substring without repeating the characters.

Example 1:

String s = “abcdabcab”
Output: 4
Explanation: The answer is “abcd”, with the length of 4.

✅ Optimal Java Solution (Time: O(n), Space: O(min(n, m)))

Here We can use the sliding window technique with a HashMap to track the index of characters.


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

public class LongestSubstring {
	
	public int lengthOfLongestSubstring(String s) {
		Map map = new HashMap<>();
		int maxLen = 0, left = 0;
		for(int right =0 ; right< s.length(); right++) {
			char current = s.charAt(right);
			if(map.containsKey(current)) {
				left = Math.max(left, map.get(current)+1);
			}
			map.put(current, right);
			maxLen = Math.max(maxLen, right-left+1);
		}
		return maxLen;
	}

	public static void main(String[] args) {
		System.out.println(new LongestSubstring().lengthOfLongestSubstring("abcdabcab"));

	}

}

✅ Explanation:

🧪 Example Input:

String s = “abcabcbb”;

✅ Step 1: Initialize Variables

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

map: Stores the most recent index of each character.
maxLen: Keeps track of the longest substring length found.
left: Left boundary of the current window (substring).

✅ Step 2: Iterate Over the String (Right Pointer)

We’ll move a pointer right from 0 to s.length() - 1.

🔄 Iteration Breakdown:

➤ `right = 0`, `char = 'a'`

'a' is not in map.
Store 'a' → 0 in map.
Window length = right - left + 1 = 1
maxLen = 1

map = { a: 0 }, left = 0, maxLen = 1.

➤ `right = 1`, `char = 'b'`

'b' is not in map.
Store 'b' → 1 in map.
Window length = 2
maxLen = 2

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

➤ `right = 2`, `char = 'c'`

'c' is not in map.
Store 'c' → 2 in map.
Window length = 3
maxLen = 3

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

➤ `right = 3`, `char = 'a'`

'a' is already in map at index 0
Move left to max(left, map.get('a') + 1) = max(0, 1) = 1
Update 'a' → 3 in map.
Window length = 3 (3 - 1 + 1)
maxLen = 3 (no change)

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

➤ `right = 4`, `char = 'b'`

'b' is at index 1
Move left = max(1, 2) = 2
Update 'b' → 4
Window length = 3
maxLen = 3

map = { a: 3, b: 4, c: 2 }, left = 2, maxLen = 3

➤ `right = 5`, `char = 'c'`

'c' is at index 2
Move left = max(2, 3) = 3
Update 'c' → 5
Window length = 3
maxLen = 3

map = { a: 3, b: 4, c: 5 }, left = 3, maxLen = 3

➤ `right = 6`, `char = 'b'`

'b' at index 4
Move left = max(3, 5) = 5
Update 'b' → 6
Window length = 2
maxLen = 3

map = { a: 3, b: 6, c: 5 }, left = 5, maxLen = 3

➤ `right = 7`, `char = 'b'`

'b' at index 6
Move left = max(5, 7) = 7
Update 'b' → 7
Window length = 1
maxLen = 3

map = { a: 3, b: 7, c: 5 }, left = 7, maxLen = 3

✅ Final Answer:

return maxLen = 3

✅ Why do we calculate `right - left + 1`?

right - left: distance between two pointers (exclusive of the first one)
right - left + 1: distance including both left and right indexes → the actual substring length

JAVA8 Code


import java.util.*;
import java.util.stream.IntStream;

public class Java8Style {
    public int lengthOfLongestSubstring(String s) {
        Map map = new HashMap<>();
        final int[] left = {0};
        return IntStream.range(0, s.length())
            .map(right -> {
                char c = s.charAt(right);
                if (map.containsKey(c)) {
                    left[0] = Math.max(left[0], map.get(c) + 1);
                }
                map.put(c, right);
                return right - left[0] + 1;
            })
            .max()
            .orElse(0);
    }
}