Longest Substring Without Repeating Characters

Medium

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

Example 1:

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

Example 2:

Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Example 4:

Input: s = ""
Output: 0

Constraints:

  • 0 <= s.length <= 5 * 104
  • s consists of English letters, digits, symbols and spaces.

Approach : Sliding Window

class Solution {
     public int lengthOfLongestSubstring(String s) {
        
        if( s == null || s.isEmpty()){
            return 0;
        }
        int l = 0, r = 0 , max_length = 0;
        Set<Character> seen = new HashSet<>();
        int n = s.length();
        while( r < n){
            char cur = s.charAt(r);
            if(!seen.contains(cur)){
                seen.add(cur);
                r++;
                max_length = Math.max(max_length, (r-l));
            }else{
                char to_remove = s.charAt(l);
                seen.remove(to_remove);
                l++;
            }
        }
        return max_length;
    }
}

Complexity Analysis

  • Time Complexity : O(2n)=O(n). In the worst case each character will be visited twice by i and j.
  • Space Complexity : O(min(m,n)). Same as the previous approach. We need O(k) space for the sliding window, where k is the size of the Set. The size of the Set is upper bounded by the size of the string n and the size of the charset/alphabet m.

Categories: String

Tagged as: ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s