Longest Substring Without Repeating Characters - Java Solution

1. Introduction

Exploring the Longest Substring Without Repeating Characters problem, a common challenge in string manipulation. It requires identifying the maximum length of a substring in a given string 's' that does not contain any repeating characters.

Problem

Given a string 's', the task is to find the length of the longest substring without repeating characters.

2. Solution Steps

1. Initialize a hash set to store characters of the current window of the substring.

2. Use two pointers (i and j) to define the sliding window's boundaries.

3. Expand the window by moving the right pointer (j) and adding new characters to the set.

4. If a duplicate character is encountered, contract the window by moving the left pointer (i) and removing characters.

5. Continuously update the maximum length of the substring found.

6. Return the maximum length after processing the entire string.

3. Code Program

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

public class LongestSubstringWithoutRepeating {
    public static void main(String[] args) {
        // Test the function with example inputs
        System.out.println(lengthOfLongestSubstring("abcabcbb")); // Example 1
        System.out.println(lengthOfLongestSubstring("bbbbb"));    // Example 2
        System.out.println(lengthOfLongestSubstring("pwwkew"));   // Example 3
    }

    // Function to find the length of the longest substring without repeating characters
    public static int lengthOfLongestSubstring(String s) {
        Set<Character> set = new HashSet<>(); // Create a hash set to store unique characters
        int maxLength = 0; // Variable to store the max length of substring found
        int i = 0; // Left pointer for the sliding window
        int j = 0; // Right pointer for the sliding window

        // Iterate over the string until the right pointer reaches the end
        while (j < s.length()) {
            if (!set.contains(s.charAt(j))) {
                // If the character is not in the set, add it and move right pointer
                set.add(s.charAt(j++));
                // Update the max length found so far
                maxLength = Math.max(maxLength, j - i);
            } else {
                // If a duplicate is found, remove the leftmost character and move left pointer
                set.remove(s.charAt(i++));
            }
        }
        // Return the maximum length of substring found
        return maxLength;
    }
}

Output:

3
1
3

Explanation:

1. lengthOfLongestSubstring: Implements a sliding window approach with two pointers and a hash set.

2. Expands the window by adding characters to the set and moving the right pointer, j.

3. If a duplicate character is encountered, contracts the window by removing characters from the left and moving the left pointer, i.

4. Continuously updates the maxLength variable with the longest unique substring found.

5. Once the right pointer reaches the end of the string, returns the maximum length of the substring without repeating characters.