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;
      for(i=0;i<s.length();i++){
        if(dict[s.charAt(i)]==0) ret++;
        else{
          int tmp = i+1-dict[s.charAt(i)];
          if(ret>=tmp) ret=tmp;
          else ret++;
        }
        dict[s.charAt(i)]=i+1;
        maxret = maxret<ret?ret:maxret;
      }
      return maxret;
    }

  • -1
    G

    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.