Leetcode problem: Longest Substring Without Repeating Characters

Today’s problem is a common but tricky one!

I will explain the problem in this challenge and provide two solutions with explanations.

URL: https://leetcode.com/problems/longest-substring-without-repeating-characters/description/

Given a string s, the task is to find the length of the longest substring that contains no repeating characters.

?? Problem Explanation:

We need to determine the maximum length of a substring without duplicate characters. For example:

1?? Input: s = "abcabcbb"

Output: 3
Explanation: The longest substring without repeating characters is "abc", which has a length of 3.

2?? Input: s = "bbbbb"

Output: 1
Explanation: The longest substring is "b", with a length of 1.

3?? Input: s = "pwwkew"

Output: 3
Explanation: The longest substring without repeating characters is "wke", with a length of 3.
(Note that “pwke” is not a valid substring, as it is a subsequence.)


?? Constraints:

? 0 <= s.length <= 50,000

? s consists of English letters, digits, symbols, and spaces.        

?? How Can We Solve It Efficiently?

This problem can be solved efficiently using the sliding window technique. The idea is to maintain a window that expands with each character while ensuring the characters within the window are unique.

Steps:

1. Use two pointers (left and right) to represent the current window.

2. As we slide the right pointer across the string, we check if the character already exists in the window. If so, move the left pointer to the right to remove the repeated character.

3. Keep track of the maximum length of substrings encountered during the iteration.

Solution #1:

We will use a Map to store the characters already found along with their positions in the provided string.

Each time, we will check the map for the character’s existence. If it exists and falls within the range of the current substring, we will move the left pointer to the position after the last occurrence of that character, which we retrieve from the map.

In each iteration, we will calculate the length of the substring using right - left + 1 and update the map with the current character’s position.

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int max=0;
        int left=0;
        Map<String,Integer> historyMap = new HashMap<>();
            
        for (int right=0;right<s.length();right++){
             String character = String.valueOf(s.charAt(i));
             if (historyMap.containsKey(character) && historyMap.get(character) >= left)      
             {
                 left=historyMap.get(character)+1;
             }
             max=Math.max(max,right-left+1);
             historyMap.put(character,rigth);
 
         }
        return max;
    }
}        

Solution #2:

This approach is a bit trickier because we only use the current string without any collection to store helper data.

We will use the String.substring() method to grab the part of the string we want.

In each iteration, we will extend the right pointer and use the String.indexOf() method to check if the character is already present. (Note: The indexOf() method returns -1 if the character is not found in the string, otherwise, it returns the position in the current substring.)

Based on the substring and the index, we can easily solve the problem.

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int max=0;
        int left=0;

        for (int right=0;right<s.length();right++){
            String part = s.substring(left,right);
            int index = part.indexOf(s.charAt(right));

            if (index!=-1){
                left=left+index+1;
            }
            max=Math.max(max,rigth-left+1);
        }

        return max;
    }
}        

? Time Complexity for both solutions: O(n), where n is the length of the string.

These approaches ensure we only traverse the string once, making them an optimal solution.

#leetcode #codingchallenge #programming #algorithms #softwareengineering #javaprogramming