Solution without hashmap, O(n) complexity


  • 0
    W
    public class Solution {
        public int lengthOfLongestSubstring(String s) {
            int[] index = new int[256];
            int max=0, size=0, base=0;
            for(int i=0; i<s.length(); i++){
                if(index[s.charAt(i)]==0||index[s.charAt(i)]<base){
                    index[s.charAt(i)] = i+1;
                    size++;
                    if(size>max)
                        max = size;
                }else{
                    size = i-index[s.charAt(i)]+1;
                    base = index[s.charAt(i)]+1;
                    index[s.charAt(i)] = i+1;
                }
            }
            return max;
        }
    }
    

    This code can solve this problem without using hash map.
    The idea is simple, using a base variable to track the start of string, and using an array index to track the last appearance of one character.


Log in to reply
 

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