How do I increase the memory efficiency of this longest substring implementation? (C++)

Question

I'm practicing my coding on leetcode.

I implemented the following algorithm to solve the longest substring problem:

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int max = 0; 
        int start = 0;  
        int rec = 0;
        int curs = 0;  
        
        char p; 
        char q; 
        
        //p = string[0]; 
        
        if(s.size() == 1){
            return 1; 
        }
        
        if(s.size() == 0){
            return 0; 
        }
        
        while(start < s.size()-1){
            // Fresh map for every "starting" key we try
            unordered_map<char, int> umap;
            while(curs < s.size()){
                if(umap.find(s[curs])==umap.end()){
                    //String does not exist
                    umap[s[curs]] = 0; 
                    rec++; 
                    
                    
                }else{
                    //The string does exist. We found a double.
                    
                    if(umap.size() > max){
                        max = umap.size(); 
                    }
                     
                    break;
                }
                
                if(curs == (s.size()-1)){
                    //we made it to the end without a double.
                    if (umap.size() > max) {
                        max = umap.size();
                    }
                    
                    return max; 
                    
                    
                }
                
                curs++; 
            }
            
            start++; 
            curs = start;
               
        
        }
        
        return max; 
    }
};

I noticed I did not rank high in memory efficiency. Can you all suggest some ways to improve memory usage in my solution?

Would it help for me to clear out the hashmap in place in order to avoid allocating it each time?

Is there somewhere where I am inadvertently copying data by not using references?

I am aware there is a similar question at Leetcode longest substring without repeating characters but my code / algorithm is pretty different from that author's question.

I am also open to other critiques of my code unrelated to the question I specifically asked.

Thank you so much.

Answer 1

Use a std::bitset

A std::unordered_map is inappropriate here. First of all, it stores keys and values, but you are not interested in the value, only if the key is in the map. Therefore, a std::unordered_set would have been better. But these containers can handle arbitrary keys and values, while for your problem you know exactly how many possible keys there are: 256 (assuming CHAR_BIT == 8). So you can make a std::bitset instead to track which characters you have already seen. As the name implies, it only uses a single bit per element, so for 256 possible characters, it only needs 32 bytes, which is likely even less than an empty std::unordered_map takes.