Java Solution O(n) time O(1) space


  • 1
    X

    The idea is to use an array to store the indices of characters and update if the character repeats. When the character repeats, update the maximum length and a previous pointer that tells the start of non-repeating substring.
    By initializing all elements in the array to -1, we know the character repeats if the element is greater than or equal to the previous(0 initially), as the minimal index of the array is 0.

    public int lengthOfLongestSubstring(String s) {
            if (s == null || s.length() == 0) {
                return 0;
            }
    	int[] dict = new int[256];
            for (int i = 0; i < dict.length; ++i) {
                dict[i] = -1;
            }
    
    	int prev = 0;
            int max = 0;
            for (int i = 0; i < s.length(); ++i) {
                int key = (int)s.charAt(i);
                if (dict[key] >= prev) {
                    max = i - prev > max ? i - prev : max;
                    prev = dict[key] + 1;
                }
                dict[key] = i;
            }
            max = s.length() - prev > max ? s.length() - prev : max;
            return prev == 0 ? s.length() :	max;
        }
    

  • 0
    G

    Pretty clever!

    
      public int lengthOfLongestSubstring(String s) {
            if (s == null || s.length() < 1) return 0;
            char[] cArr = s.toCharArray();
            int dict[] = new int[256], sum = 0, prev = 0, i, len = cArr.length;
            Arrays.fill( dict, -1 );
            for (i = 0; i < len; i++ ){
                int c = cArr[i];
                if (dict[c] >= prev){
                    sum = Math.max(i - prev, sum);
                    prev = dict[c] + 1;
                }
                dict[c] = i;
            }
            return Math.max( i - prev, sum);
        }
    

Log in to reply
 

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