# Brute force vs optimized solution

• 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;
}
}

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