Longest Substring Without Repeating Characters Leetcode Solution

Problem Statement

The Longest Substring Without Repeating Characters LeetCode Solution –  states that given the string s. We need to find the longest substring without repeating characters.

Example:

Input:  s = "abcabcbb"

Output: 3

Explanation:

• The longest substring with no characters being repeated is of length 3.
• The string is: “abc”.

Input:  s = "bbbbb"

Output: 1

Explanation:

• All the characters are the same hence, the longest substring with no characters being repeated is of length 1.

Approach

Idea:

1. The main idea to solve this problem is to use Hashmap.
2. We can also use the brute force approach to consider every substring and check whether the substring contains all the distinct characters. The Brute force approach will give a time limit exceeded verdict since the maximum size of the array is 5 * 10^4.
3. Keep a hashmap that stores the characters in strings as keys and their positions as values, and keep two pointers that define the max substring.
4. Move the right pointer to scan through the string, and meanwhile update the hashmap.
5. If the character is already in the hashmap, then move the left pointer to the right of the same character last found. Note that the two pointers can only move forward.
6. Finally, we’ll have a length of the longest substring with all characters different.

Code

Longest Substring Without Repeating Characters C++ Solution:

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        vector<int> occ(260,-2);
        int n = s.length(),ans = 0,j = 0;
        for(int i=0;i<n;i++){
            if(occ[s[i]]==-2){
                ans = max(ans,i-j+1);
            }
            else{
                while(j<=occ[s[i]]){
                    occ[s[j++]] = -2;
                }
            }
            occ[s[i]] = i;
        }
        return ans;
    }
};

Longest Substring Without Repeating Characters Java Solution:

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s.length()==0) return 0;
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        int max=0;
        for (int i=0, j=0; i<s.length(); ++i){
            if (map.containsKey(s.charAt(i))){
                j = Math.max(j,map.get(s.charAt(i))+1);
            }
            map.put(s.charAt(i),i);
            max = Math.max(max,i-j+1);
        }
        return max;
    }
}

Complexity Analysis:

Time Complexity

The time complexity of the above code is O(N) if we use a vector of sufficient size to keep track of the occurrence of characters or a good hash function that allows insertions and deletions in constant time, where N = the size of the input string.

Space Complexity

The space complexity of the above code is O(M) where M = size of the hashmap. Hashmap stores the entries of characters. The Space Complexity of the solution totally depends on the hashmap. Space Complexity will be more if the size of the hashmap is more.