Longest Substring Without Repeating Characters

We have a string s of length l. Find the longest substring that contain no repeating characters. Return the length of the longest substring simply.

Example

String s = “abcabcbb”

We can see that substrings “abc” (index 0 to 2) and “bca” (index 1 to 3)  and "cab" (index 2 to 4) have the length of 3 and doesn't have a repeating element. So, the maximum length of substring with no repeating characters is 3.

Idea

Since we have to find the longest substring, we will need to capture length while we are processing the string. To capture length, we will use two pointers - left & right. We will also need some way to store the visited character to be able to check is a character is getting repeated or not. For this we can use a HashSet or a Map. We can also use a boolean array of 256 character length which can be space efficient for larger input.

• Both pointers will be initialized at index 0 which is the first character of string.
• Pointer right will be incremented by 1 for each iteration.
• If the character at pointer right has not appeared before, we will calculate the length of substring (right - left + 1).
• If a character repeates at index r, we will need to update the position of pointer left so that it starts after the first occurrence of repeated character.
• This way the new length of characters(right - left) will not posses the repeated character.

Complexity

• Time Complexity: O(N), where N is the size of the array
• Space Complexity: O(N), where N is the size of the array

Java Code

import java.util.*;

class LongestSubstring{
	public int lengthOfLongestSubstring(String str) {

        Map<Character, Integer> subString = new HashMap<>();

        int left = 0;
        int right = 0;
        int maxLength = 0;
        int length = 0;


        while (right < str.length()) {
            
            if (subString.containsKey(str.charAt(right))) {
                left = Math.max(left, subString.get(str.charAt(right)) + 1);
            }

            subString.put(str.charAt(right), right);
            length = right - left + 1;
            maxLength = Math.max(maxLength, length);

            right++;
        }
        return maxLength;
    }

    public static void main(String[] args) {
        LongestSubstring longestSubstring = new LongestSubstring();
        System.out.println("Length of Longest Substring without Repeating Character is: "
                + longestSubstring.lengthOfLongestSubstring("abcabcbb"));
    }
}

Output

Length of Longest Substring without Repeating Character is: 3