Java O(n) time complexity with O(1) space


  • 0
    R

    public class Solution {
    public int lengthOfLongestSubstring(String s) {
    if (s == null || s.length() == 0) {
    return 0;
    }

        int len = 1;
        int[] charArray = new int[256];
        int j = 0;
        for (int i = 0; i < s.length(); i++) {
            while (j < s.length()) {
                
                // if there is already such char, dup detected, break and calculate len
                if (charArray[s.charAt(j)] == 1) {
                    break;
                } else {
                    charArray[s.charAt(j)]++;
                }
                
                ++j;
            }
            
            len = Math.max(len, j - i);
            
            // Move char of index i out of the window, so in while (j < s.length()) check again
            charArray[s.charAt(i)]--;
        }
        
        return len;
    }
    

    }


Log in to reply
 

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