Solving the Longest Substring Without Repeating Characters Problem in Java | O(n) Time Complexity

Problem Definition

Given a string, find the length of the longest substring without repeating characters.

Input: A single string s.

Output: An integer representing the length of the longest substring without repeating characters.

Constraints:

• 0 ≤ s.length ≤ 5 * 10⁴
• The string consists of English letters, digits, symbols, and spaces.

Example:

    Input: "abcabcbb"
    Output: 3
    Explanation: The answer is "abc", with the length of 3.
    

Understanding the Problem

The core challenge of this problem is to find the longest substring without repeating characters. This problem is significant in various applications such as text processing, data compression, and more. A common pitfall is to overlook the need for an efficient solution, especially given the potential length of the input string.

Approach

To solve this problem, we need to consider different approaches:

Naive Solution

The naive solution involves checking all possible substrings and determining if they contain repeating characters. This approach is not optimal due to its high time complexity of O(n³).

Optimized Solution

An optimized approach uses the sliding window technique with a hash map to keep track of characters and their positions. This allows us to efficiently find the longest substring without repeating characters in O(n) time complexity.

Algorithm

Here is a step-by-step breakdown of the optimized algorithm:

1. Initialize a hash map to store characters and their latest positions.
2. Use two pointers, start and end, to represent the current window of characters.
3. Iterate through the string with the end pointer.
4. If the character at the end pointer is already in the hash map, move the start pointer to the right of the previous position of this character.
5. Update the hash map with the current position of the character.
6. Calculate the length of the current window and update the maximum length if necessary.

Code Implementation

import java.util.HashMap;

public class LongestSubstringWithoutRepeating {
    public int lengthOfLongestSubstring(String s) {
        // HashMap to store the last positions of each character
        HashMap<Character, Integer> map = new HashMap<>();
        int maxLength = 0;
        int start = 0;

        for (int end = 0; end < s.length(); end++) {
            char currentChar = s.charAt(end);

            // If the character is already in the map, move the start pointer
            if (map.containsKey(currentChar)) {
                start = Math.max(start, map.get(currentChar) + 1);
            }

            // Update the last position of the current character
            map.put(currentChar, end);

            // Calculate the length of the current window
            maxLength = Math.max(maxLength, end - start + 1);
        }

        return maxLength;
    }

    public static void main(String[] args) {
        LongestSubstringWithoutRepeating solution = new LongestSubstringWithoutRepeating();
        System.out.println(solution.lengthOfLongestSubstring("abcabcbb")); // Output: 3
        System.out.println(solution.lengthOfLongestSubstring("bbbbb")); // Output: 1
        System.out.println(solution.lengthOfLongestSubstring("pwwkew")); // Output: 3
    }
}

Complexity Analysis

The time complexity of the optimized solution is O(n) because each character is processed at most twice (once by the end pointer and once by the start pointer). The space complexity is O(min(n, m)), where n is the length of the string and m is the size of the character set.

Edge Cases

Consider the following edge cases:

• Empty string: The output should be 0.
• String with all identical characters: The output should be 1.
• String with no repeating characters: The output should be the length of the string.

Examples:

    Input: ""
    Output: 0

    Input: "aaaaa"
    Output: 1

    Input: "abcdef"
    Output: 6
    

Testing

To test the solution comprehensively, consider a variety of test cases:

• Simple cases with short strings.
• Cases with mixed characters (letters, digits, symbols).
• Edge cases as discussed above.

Using a testing framework like JUnit can help automate and manage these tests effectively.

Thinking and Problem-Solving Tips

When approaching such problems, consider the following tips:

• Break down the problem into smaller parts and understand each part.
• Think about different approaches and their trade-offs.
• Practice similar problems to improve problem-solving skills.

Conclusion

In this blog post, we discussed how to solve the Longest Substring Without Repeating Characters problem in Java using an optimized O(n) time complexity solution. Understanding and solving such problems is crucial for improving algorithmic thinking and coding skills. Keep practicing and exploring further to master these concepts.

Additional Resources

For further reading and practice, consider the following resources:

• LeetCode Problem
• GeeksforGeeks Article
• Coursera Algorithms Course