11-line simple Java solution, O(n) with explanation


  • 396

    the basic idea is, keep a hashmap which stores the characters in string as keys and their positions as values, and keep two pointers which define the max substring. move the right pointer to scan through the string , and meanwhile update the hashmap. 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.

       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;
        }

  • -54
    R

    this is not O(n) as we have the complexity of searching in hashmap


  • 35
    L

    Hi, can you explain this line please:
    j = Math.max(j,map.get(s.charAt(i))+1);
    I cannot figure why you need to move this pointer (j) to either j or to the position of the last found repeating character.
    Many thanks!


  • 5
    T

    Hashmap has O(n) complexity in worse cases, so the total complexity is still O(n)


  • 16
    T

    The variable "j" is used to indicate the index of first character of this substring. If the repeated character's index is less than j itself, which means the repeated character in the hash map is no longer available this time


  • 1
    J

    But you will use hashmap to search n times.


  • 1
    A

    this is genious


  • 10
    Q

    Hashmap search in O(1)


  • 4
    T
    public int lengthOfLongestSubstring(String s) {
    	int[] arr= new int[256];
    
    	int record = 0;
    	if (s != null && s.length() > 0)
    		record = 1;
    	else
    		return 0;
    	int lastIndex =0;
    	for (int i = 0; i < s.length(); i++) {
    			int code = (int)s.charAt(i);
    		
    		if (arr[code] != 0 ) {
    			int index = arr[code]-1;
    			int len =i -lastIndex;
    			if(len >record) record =len;
    			if(index >= lastIndex)
    			lastIndex = index+1;
    		} 
    		arr[code] =i+1;
    	}
    	if(s.length()- lastIndex >record) record =s.length() - lastIndex ;
    
    	return record;
    }

  • 4

    I think there is no need to update longest evey time:

    class Solution {
    public:
        int lengthOfLongestSubstring(std::string s) {
            std::vector<int> flag(256, -1);
            int start = 0, longest = 0, len = s.size();
            for (int i = 0; i != len; ++i) {
                if (flag[s[i]] >= start) {
                    longest = std::max(longest, i - start);
                    start = flag[s[i]] + 1;
                }
                flag[s[i]] = i;
            }
            return std::max(longest, len - start);
        }
    };

  • 0
    L

    to move the left pointer to the left of the same character last found, or to move the left pointer to the right(next position) of the same character last found?


  • 2
    M

    agree, should be move the left pointer to the right of the same char last found


  • 0

    thanks @lindaxia2001 and @marcusgao for pointing that out. It was a typo.


  • 0
    Z

    no need for O(n) space. Here is an O(n) time O(1) space solution using Kadane's algorithm

    Idea is that, while we traverse form left to right if we see a character at position j is a duplicate of a character at a position i < j on the left then we know that we can't start the substring from i anymore. So, we need to start a new substring from i+1 position. While doing this we also need to update the length of current substring and start of current substring. Important part of this process is to make sure that we always keep the latest position of the characters we have seen so far. Below is a simple O(n) implementation of this logic.

    public class Solution {
        public int lengthOfLongestSubstring(String s) {
            int lastIndices[] = new int[256];
            for(int i = 0; i<256; i++){
                lastIndices[i] = -1;
            }
    
            int maxLen = 0;
            int curLen = 0;
            int start = 0;
            int bestStart = 0;
            for(int i = 0; i<s.length(); i++){
                char cur = s.charAt(i);
                if(lastIndices[cur]  < start){
                    lastIndices[cur] = i;
                    curLen++;
                }
                else{
                    int lastIndex = lastIndices[cur];
                    start = lastIndex+1;
                    curLen = i-start+1;
                    lastIndices[cur] = i;
                }
    
                if(curLen > maxLen){
                    maxLen = curLen;
                    bestStart = start;
                }
            }
    
            return maxLen;
        }
    }
    

  • 4

    Hi Zahid2, the lastIndices[] you used has asymptotically equal space as the hashmap I used, since the hashmap in this problem has at most 256 keys.


  • 23
    E

    Thanks for the intuitive answer. Here is the same algo with int[256] rather than HashMap. Faster than map and shorter code.

    public class Solution {
        public int lengthOfLongestSubstring(String s) {
            int result = 0;
            int[] cache = new int[256];
            for (int i = 0, j = 0; i < s.length(); i++) {
                j = (cache[s.charAt(i)] > 0) ? Math.max(j, cache[s.charAt(i)]) : j;
                cache[s.charAt(i)] = i + 1;
                result = Math.max(result, i - j + 1);
            }
            return result;
        }
    }

  • -2
    H

    Set structure better than HashMap because it doesn't need to count character.

    int lengthOfUniqChar(String s) {
        Set<Character> set = new HashSet<>();
        for(int i = 0; i < s.length(); i++) {
            set.add(s.charAt(i));
        }
        return set.size();
    }
    

  • 0
    N

    This is very brilliant!


  • 2

    Beautiful!
    This is easier than mine. I didn't use hashmap but instead using set by adding and erasing, it's so useful to keep the index of the last found, otherwise, I need to move left pointer until meet the same character, that's what costs me. Thanks!


  • 0
    Y
    This post is deleted!

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.