Simple O(n) solution using Java, little time consuming, but still better than 69% people so..


  • 0
    A
    public class Solution {
        public int lengthOfLongestSubstring(String s) {
            boolean values[]=new boolean[256];
            int max_count=0,j=0,temp_count=0;
            char[] array=s.toCharArray();
            for(int i=j;i<array.length;i++){
                if(!values[array[i]]){
                    temp_count++;
                    values[array[i]]=true;
                    if(temp_count>=max_count)
                        max_count=temp_count;
                }
                else{
                    temp_count=0;
                    values=new boolean[256];
                    i=j;
                    j++;
                }
            }
            return max_count;
        }
    }

  • 0
    H

    why your code is O(n) not O(n^2)? And why your code is faster than mine?

    public int lengthOfLongestSubstring(String s) {
        int[] container = new int[1 << 16];
        int start = 0;
        int max = 0;
        int tmpMax = 0;
        char[] chars = s.toCharArray();
        for (int i = 0, j = chars.length; i < j; i++) {
          int key = chars[i];
          int v = container[key];
          int index = v - 1;
          if (index < start) {
            ++tmpMax;
          } else {
            max = Math.max(max, tmpMax);
            tmpMax = i - index;
            start = index;
          }
          container[key] = i + 1;
        }
        return Math.max(max, tmpMax);
      }

Log in to reply
 

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