What's the fastest Java solution?


  • 0
    T

    I am using a ArrayList to check the repeated char. I believe it is an O(n) method. However, it took almost 300 ms.

    public int lengthOfLongestSubstring(String s) {
    List<Character> check=new ArrayList<Character>();
    int res=0;
    for(int i=0;i<s.length();i++){
    char cur=s.charAt(i);
    if(check.contains(cur)) check.subList(0,check.indexOf(cur)+1).clear();
    check.add(s.charAt(i));
    res=Math.max(res,check.size());
    }
    return res;
    }


  • 2
    Z

    Here's my solution, using an int[] array directly mapping characters and it's index. 255ms

    public int lengthOfLongestSubstring(String s) {
     int maxLength=0;
     int[] map = new int[256];
     Arrays.fill(map, -1);
     char[] a = s.toCharArray();
     int start=0;
     for (int i=0; i< a.length ; i++){
       if (map[a[i]] >= start) {
         maxLength = Math.max(maxLength, (i - start));
         start = map[a[i]] +1;
        }
        map[a[i]] = i;
      }
     return Math.max(maxLength, (a.length -start));
    }

Log in to reply
 

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