Why my hash in C++ is wrong?


  • 0
    X

    it will not pass a very long string

      class Solution {
        public:
            int lengthOfLongestSubstring(string s) {
                int answer=0;
                map<char, int> hashTable;
                hashTable.clear();
                if(s.size()==0) return 0;
                for(int i=0;i<s.size();i++){
                    if(hashTable[s[i]]!=s[i]){
                        answer++;
                        hashTable[s[i]]=s[i];
                    }
                    else continue;
                }
                return answer;
            }
        };

  • 0
    M

    You can use unordered_map instead of map. Here is my code.

    int lengthOfLongestSubstring(string s) {
            unordered_map<char, int> chMap;
            int maxLen = 0;
            int pos = -1;
            
            for(int i=0; i<s.size(); i++) {
                auto it = chMap.find(s[i]);
                if((it != chMap.end()) && (it->second >= pos)) {
                    pos = it->second;
                }
                chMap[s[i]] = i;
                maxLen = max(maxLen, i-pos);
            }
            
            return maxLen;
        }

Log in to reply
 

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