My JAVA accepted code O(n)

  • 0
    public class Solution {
        boolean[] letter;
        int maxlen = 1;
        public int lengthOfLongestSubstring(String s) {
            if (s.length() == 0) return 0;
            if (s.length() == 1) return 1;
            letter = new boolean[128]; // for ASCII encoding string, default values are all false
            int i = 0;
            letter[s.charAt(0)] = true;
            int j = 1;
            while(j < s.length()){
                if (letter[s.charAt(j)]){ // repeated character
                    while(i < j){
                        if (s.charAt(i) == s.charAt(j)){ // update i
                            letter[s.charAt(i)] = false;
                }else{ // if no repeat, the length is suceessfully advance one step
                    letter[s.charAt(j)] = true;
            return maxlen;
        private void update(int len){
            if (len > maxlen) maxlen = len;

    Instead of using HashMap to check unique characters, I use ASCII boolean array to store the substring letter existence. Step by step moving pointer j. If pointer j encounters a repeated letter, pointer i is moving until the repeated letter is cross over or i reach out j (in the same position).

Log in to reply

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