My 6ms Java solution beating 85%, with explanation

  • 5

    The main idea:

    • Scan from head, when meeting a letter:
    • If not contained, ret++, and update dict using the index of current letter.
    • In contained, remove the letters before the duplicate (inclusive). Here we don't actually need to use a loop to do the removal. We can utilize the index instead.
    • Update maxret after each iteration.

    Attached is the AC code:

    public int lengthOfLongestSubstring(String s) {
      int[] dict = new int[128];
      int ret=0, maxret=0, i;
        if(dict[s.charAt(i)]==0) ret++;
          int tmp = i+1-dict[s.charAt(i)];
          if(ret>=tmp) ret=tmp;
          else ret++;
        maxret = maxret<ret?ret:maxret;
      return maxret;

  • -1

    Great solution!, the idea is no track last occurrence index, there for no need of two pointers.

  • -1

    can this handle chinese characters?

Log in to reply

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