Anyone know what's wrong with my code


  • 1
    F

    class Solution {
    public:
    int lengthOfLongestSubstring(string s) {
    string temp="";
    int len=s.size();
    int max=0;
    //int size=0;
    for(int i=0;i<len;++i){
    size_t found=temp.find(s[i]);
    if(found==string::npos){
    temp+=s[i];
    }
    else{
    if(temp.size()>max){
    max=temp.size();
    }
    temp="";
    temp+=s[i];
    }
    }
    return max;
    }
    };


  • 0
    M

    Disclaimer: C++ is not my language

    I think you need to re-read the specification of the question. Your code appears to only pick up on the longest substring if it is at the start of the given string or completely independant of the first substring. If the longest substring starts at character 2 of the first substring then you will miss it.

    Example:

    abcaefgh

    Your algorithm produces the first candidate as "abc" length 3. Then it wipes temp and starts again at position 5 making the next candidate "efgh" length 4. 4 is returned as the result.

    The actual longest substring is "bcaefgh" length 7.

    In order to quickly hack your algorithm to work, add a new integer "j" outside the for loop. Set it to 1. Inside the for loop where you reset temp to the empty string set i=j and increment j; Total hack but it should get the correct result using your base code.

    Remember to use the code formating button when you submit next time!

    Edit:There's one other addition you need to do to to catch the case where the longest string is the last substring you encounter. I also added a simple optimisation that if you get to max length being greater than the number of characters from s[i] to sen [len-1] then you quit.

    Sorry, it's in java but you should get the gist of the algorithm. Quick hint: whilst this works, it's not very efficient and you'll not pass the time constraint with it.

            String temp="";
    		int len=s.length();
    		int max=0;
    		int j=0;
    		for(int i=0;i<len;++i){
    			String current = ""+s.charAt(i);
    			boolean found=temp.contains(current);
    			if(!found){
    				temp+=current;
    				if(i==len-1&&temp.length()>max){
    					max=temp.length(); 
    				}
    			} 
    			else{ 
    				if(temp.length()>max){ 
    					max=temp.length(); 
    				}
    				temp="";
    				i=j;
    				j++;
    				if(max>(len-i)){
    					i=len;
    				}
    			}
    
    		} 
    		return max;
    

    The trick with this one is realising that you don't actually need to use a string type to keep track of the current substring. Try using a hashmap and just remember the starting index of the first character in the current candidate substring. Spoiler below:

    public class Solution {
        public int lengthOfLongestSubstring(String s) {
    		int len=s.length();
    		int max=0;
    		int current_index = 0;
    		HashMap<Character,Character> hm = new HashMap<Character,Character>();
    		for(int i=0;i<len;++i){
    			char current_char = s.charAt(i);
    			if(!hm.containsKey(current_char)){
    				hm.put(current_char, current_char);
    			}
    			else{
    				if(hm.size()>max){ 
    					max=hm.size(); 
    				}
    				while(s.charAt(current_index)!= current_char){
    					hm.remove(s.charAt(current_index));
    					current_index++;
    				}
    				current_index++;
    			}
    		}
    		if(hm.size()>max){ 
    			max=hm.size(); 
    		}
    		return max; 
        }
    }

Log in to reply
 

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