6. Find the Longest Substring Without Repeating Characters in Java : FAANG Interviews

 Finding the longest substring without repeating characters is a widespread coding problem. This challenge effectively tests your understanding of strings and ability to apply the sliding window algorithm. In this article, we will explore an efficient solution that utilizes the sliding window technique and a HashMap to keep track of the frequency of characters.

Problem Overview

Given a string, you are tasked with finding the length of the longest substring that contains no repeating characters. For example:

• Input: "abcabcbb"
• Output: 3 (The answer is "abc" with length 3.)

Key Concepts

Before diving into the code, let's outline the key concepts that will help us solve the problem:

1. Sliding Window Algorithm:
   • The sliding window technique involves maintaining a "window" of valid elements, which dynamically adjusts as we traverse the string.
   • As we iterate through the string, we try to extend the window by including new characters, but we also shrink the window from the left if we encounter a repeating character.
2. HashMap for Character Frequency Counting:
   • We utilize a HashMap, or a similar data structure, to store the frequency of characters within the current window. This allows us to quickly determine if a character is already in the window and make adjustments as needed.
3. Time Complexity Optimization (O(n)):
   • A brute force approach would involve checking every possible substring, resulting in a time complexity of O(n²). However, by employing the sliding window technique, we can achieve a linear time complexity of O(n), where n represents the length of the input string. This improvement allows us to handle even large strings efficiently.

Solution Approach

    The core concept of this solution involves using two pointers (or indices) to represent the left and right ends of a sliding window. The right pointer expands the window by adding new characters, while the left pointer shrinks the window whenever a repeating character is encountered.

Here’s the step-by-step breakdown of the approach:

1. Use a HashMap to store the most recent index of each character in the string.
2. Iterate through the string using a right pointer, extending the window.
3. If a character repeats, move the left pointer just past the last occurrence of that character to maintain a substring with unique characters.
4. Keep track of the maximum length of the substring without repeating characters.

Code Implementation

Below is the Java code that implements the solution:

import java.util.HashMap;

public class LongestSubstringWithoutRepeatingCharacters {

    public static int lengthOfLongestSubstring(String s) {

        // HashMap to store the last position of each character.

        HashMap<Character, Integer> map = new HashMap<>();

        
        // Initialize pointers for the sliding window.

        int left = 0; // Left pointer

        int maxLength = 0; // To keep track of the maximum length

        
        // Iterate through the string with the right pointer.

        for (int right = 0; right < s.length(); right++) {

            char currentChar = s.charAt(right);


            // If the character is already in the HashMap and its position is greater than or equal to 'left',

            // move 'left' pointer to the right of the last occurrence of the current character.

            if (map.containsKey(currentChar) && map.get(currentChar) >= left) {

                left = map.get(currentChar) + 1;

            }


            // Update the last seen position of the current character.

            map.put(currentChar, right);

            
            // Calculate the maximum length of the substring without repeating characters.

            maxLength = Math.max(maxLength, right - left + 1);

        }

        
        return maxLength;

    }

    public static void main(String[] args) {

        String input = "abcabcbb";

        System.out.println("Length of Longest Substring Without Repeating Characters: " + lengthOfLongestSubstring(input));

    }

}

Explanation of the Code

1. HashMap Initialization:
   • We create a HashMap<Character, Integer> to store the last seen index of each character in the string.
2. Sliding Window Logic:
   • We maintain two pointers: left and right. The right pointer moves from the start to the end of the string.
   • If we encounter a repeating character within the window, the left pointer is moved to the right of the last occurrence of that character.
3. Update Maximum Length:
   • After processing each character, we calculate the current length of the substring as right-left + 1. The maxLength is updated with the maximum of its current value and the new substring length.
4. Edge Cases:
   • The code handles cases where the string is empty or contains only one character.

Time and Space Complexity

• Time Complexity: O(n)
  • We iterate over the string once with the right pointer and move the left pointer as needed, each only once. Hence, the time complexity is linear in terms of the string size.
• Space Complexity: O(min(n, m))
  • The space complexity depends on the size of the HashMap, which stores the last seen index of each character. The maximum size of the map is determined by the number of distinct characters in the string (m), which could be at most n if all characters are unique.

Summary

   This approach effectively addresses the problem of finding the longest substring without repeating characters using the sliding window technique. By employing a HashMap to track the last seen index of each character, we ensure that the solution operates in linear time, making it suitable for significant inputs. This method exemplifies how to optimize solutions for string manipulation challenges.

Please stay tuned; I will update Point 6 of the FANNG Interview series; please check the top 10 interview questions here.

Happy coding!