Longest Substring without Repeating Characters | Code with kamlesh

Introduction:
In the realm of string manipulation problems, finding the longest substring without repeating characters is a classic challenge. This problem requires us to identify the maximum length of a substring within a given string, where no character appears more than once. In this blog post, we will delve into the details of this problem, understand the underlying algorithmic approach, and implement a solution in the Java programming language.

Problem Statement:
Given a string, we are tasked with finding the length of the longest substring that does not contain any repeating characters.

Algorithmic Approach:
To solve this problem efficiently, we can use the “sliding window” approach. The basic idea is to maintain a window of characters and move it while ensuring that no repeating character is present within the window. This approach allows us to optimize the process of identifying the longest substring without starting from scratch for each position in the string.

Here are the steps of the algorithm:

1. Initialize two pointers, “start” and “end,” both pointing to the beginning of the string.
2. Create a hash set to store the characters within the current window.
3. Iterate through the string using the “end” pointer:
   a. If the character at the “end” pointer is not in the hash set, add it and move the “end” pointer to the right.
   b. If the character is already in the hash set, remove the character at the “start” pointer from the hash set and move the “start” pointer to the right.
4. Keep track of the maximum length of the substring as you move the pointers.
5. Return the maximum length once the iteration is complete.

Java Implementation:

public class LongestSubstringWithoutRepeating {

    public static int lengthOfLongestSubstring(String s) {
        int n = s.length();
        int maxLength = 0;
        Set<Character> charSet = new HashSet<>();
        int start = 0, end = 0;

        while (end < n) {
            if (!charSet.contains(s.charAt(end))) {
                charSet.add(s.charAt(end));
                maxLength = Math.max(maxLength, end - start + 1);
                end++;
            } else {
                charSet.remove(s.charAt(start));
                start++;
            }
        }

        return maxLength;
    }

    public static void main(String[] args) {
        String input = "abcabcbb";
        int result = lengthOfLongestSubstring(input);
        System.out.println("Length of longest substring without repeating characters: " + result);
    }
}

Conclusion:
In this blog post, we explored the problem of finding the longest substring without repeating characters. We discussed the sliding window algorithmic approach and implemented a solution in the Java programming language. This problem is a great example of how efficient algorithms and data structures can be used to tackle real-world string manipulation challenges. By understanding and implementing such solutions, developers can enhance their problem-solving skills and algorithmic thinking.