Brute force vs optimized solution


  • 0
    N

    The first one is a brute force approach that uses nested for loops. While it gets the job di=one its pretty inefficient as its complexity is around O(n2) (Big O of n squared). This submission showed that this solution was in the bottom 10%.

    
    /* Runtime: 113 ms */
    
        public class Solution {
            public int lengthOfLongestSubstring(String s) {
                ArrayList<String> result = new ArrayList();
                char[] word = s.toCharArray();
                int maxLen = 0;
                int len=0;
                int size=s.length();
                HashMap letters = new HashMap();
    
                if(size <=0 )
                    return size;
    
                for(int i=0 ; i< size; i++){
                    letters.clear();
                    len=0;
    
                    for(int j=i ; j<size ; j++){
                        if(letters.containsKey(word[j])){
                            break;
                        }else{
                            letters.put(word[j],1);
                            len++;
                            if(len > maxLen)
                                maxLen =len;
                        }
                    }
                }
    
                return maxLen;
            }
        }
    
    

    The second one is optimized in the sense that it scans the string only once. I got rid of the nested loop . This solution is better that 50% of the submissions in LeetCode, still not the best. The complexity should be close to O(n) . Not exactly sure though. But its definitely not exponential.

    
        /* Runtime: 41 ms */
        public class Solution {
            public int lengthOfLongestSubstring(String s) {
    
                int maxLen = 1;
                int size=s.length();
                int[] charMap = new int[256];
                int startPoint = 0;
                int ptr = 0;
    
    
                for(int i=0; i<256; i++){
                    charMap[i] = -1;
                }
    
                if(size < 2)
                    return size;
    
                while(ptr < size){
                    /* If not repeated*/
                    if(charMap[s.charAt(ptr)] == -1){
                        /* save index */
                        charMap[s.charAt(ptr)] = ptr;
                        maxLen = Math.max(maxLen, (ptr - startPoint) + 1 );
                    }else{ /* Repeated */
                        if(startPoint <= charMap[s.charAt(ptr)])
                            startPoint =  charMap[s.charAt(ptr)] + 1;
    
                        charMap[s.charAt(ptr)] = ptr;
                        maxLen = Math.max(maxLen, (ptr - startPoint) + 1);
                    }
    
                    ptr++;
                }
    
    
                return maxLen;
            }
        }
    
    
    
    
    

Log in to reply
 

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