Share my Java solution using HashSet


  • 128

    The idea is use a hash set to track the longest substring without repeating characters so far, use a fast pointer j to see if character j is in the hash set or not, if not, great, add it to the hash set, move j forward and update the max length, otherwise, delete from the head by using a slow pointer i until we can put character j to the hash set.

    public int lengthOfLongestSubstring(String s) {
        int i = 0, j = 0, max = 0;
        Set<Character> set = new HashSet<>();
        
        while (j < s.length()) {
            if (!set.contains(s.charAt(j))) {
                set.add(s.charAt(j++));
                max = Math.max(max, set.size());
            } else {
                set.remove(s.charAt(i++));
            }
        }
        
        return max;
    }

  • 0
    Y
    This post is deleted!

  • 3
    H

    I am not able to understand why there is a while loop in the else part. I tried to remove that and still got AC. May be the test cases didn't cover all the possible scenarios. For what input would that be required? Thanks.


  • 3

    Hi harish-v, you are absolutely right! I have removed the redundant while loop, now the code is much more cleaner. Thank you so much! :)


  • 3
    S

    I am sorry I can not understand it. if the input is "abcbc", then when j==3, set contains it. but you remove the "a", how can it be right?


  • 5

    Hi shadow7429, I understand what you try to achieve, basically when we see the 2nd 'b', we should be able to move the slow pointer i to the 1st 'c' in O(1) time, but to do that, as far as I know, we need to borrow LRU data structure, I agree that's a faster way, but I would rather keep the solution easy to read.

    Back to your question, after we remove 'a', we still can't put the 2nd 'b' to the set, so we keep removing the 1st 'b', now the slow pointer comes to the 1st 'c'. It's like we are using an adjustable window to find the longest substring without repeating characters.


  • 0
    H

    once find a contained character, U should clean the set preparing for the next series of substring. But the old substring's length was maintained in the "max". So don't worry about it.


  • 0
    A

    Great thoughts!
    I tried to surround the while loop with an if statement, that to see if (s.length() - i > j), which meas if what is left is already shorter than what we have got, the max length is the current max; no need to check on the rest.

    if (s.length() - i > j) {
    while (j < s.length()) {
    if (set.add(s.charAt(j))) {
    j++;
    max = Math.max(max, set.size());
    } else {
    set.remove(s.charAt(i++));
    }
    }
    }


  • 3
    J

    if we use hashmap to store the position of occured characters. Then we don't need to find the next start position by set.remove(s.charAt(i++)); .
    We just put i = map[s[j]] + 1


  • 1
    E

    Awesome solution, this was my intuition as well but I got caught on getting the return value, getting the set.size() was what I was missing!

    p.s. you can simplify the if condition to if (set.add(s.charAt(j))) { as set's add method returns true only if the item was added and false if it was a dup


  • 0
    X

    good idea and it's easy for me to understand~,thanks


  • 0
    C

    @jeantimex brilliant!


  • 0
    L

    good @jeantimex


  • 0
    Y

    very smart !!!


  • 0
    J

    @jeantimex said in Share my Java solution using HashSet:

    Hi shadow7429, I understand what you try to achieve, basically when we see the 2nd 'b', we should be able to move the slow pointer i to the 1st 'c' in O(1) time, but to do that, as far as I know, we need to borrow LRU data structure, I agree that's a faster way, but I would rather keep the solution easy to read.

    @shadow7429
    https://discuss.leetcode.com/topic/8232/11-line-simple-java-solution-o-n-with-explanation/2

    That's why in the other solution, a HashMap is used to record the character's previous position so that it can skip over.

    This solution would be O(2n) in the worse case, I believe.
    input -> "abcdefga",
    j would increase input.length() times while i would increase input.length() - 1 times


  • 1

    Very easy to understand! Thanks :)


  • 0
    J

    @harish-v Hi, I think the while loop still need, otherwise cannot pass the test case: "tmmzuxt"


  • 0
    B

    @jybxxzj I agree with you!


  • 0
    C
    This post is deleted!

  • 0
    A

    fantastic idea,I understand it now,Thanks


Log in to reply
 

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