CODEWITHSUNDEEP
c++
林子軒
林子軒

Reputation: 1

how can I make this C++ code more efficient

This is a leetcode question about " Longest Substring Without Repeating Characters" and I failed on 987th (It is the final test case) the reason i fail is because "Time Limit Exceeded"

Can someone give me some advice to fix my code? 

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        vector<char> answer;
        vector<char> temp;
        int len = s.length();
        for ( int a = 0; a < len;a++ ){
            for( int aa = a; aa < len;aa++ ){
                temp.push_back(s[aa])    ;        
                if ( repeat(temp) ){
                    temp.pop_back();
                    changeAnswer(temp,answer);
                    temp.clear();
                    aa = len;
                }
                changeAnswer(temp,answer);
            }
        }


        return answer.size();
    }

    bool repeat(vector<char> temp){
        if ( temp.size() < 2 )
            return false;
        for ( int a = 0; a < temp.size();a++ )
            for ( int aa = a+1; aa < temp.size(); aa++ )
                if ( temp[aa] == temp[a] )
                    return true;
        return false;
    }

    void changeAnswer( vector<char> &temp, vector<char> &answer ){
        if ( temp.size()>answer.size() )
             answer = temp;

    }
};

Upvotes: 0

Views: 112

Answers (1)

Madhur Vashistha
Madhur Vashistha

Reputation: 329

It looks that you are using a complete brute force approach to solve the question. The time complexity of your solution is O(n^2), if 'n' is the length of the string. In the case of string length being in range 10^5, the time limit will definitely exceed. First, you should try to optimize your code to make it work in O(n) time. Here is what you can do: I think hashing would be helpful in this case. You can store the last occurrence of a character in a hashMap or unordered_map and check the current character if it is already there in the map. If so, you need to count only the characters after the last occurrence of this character. To keep track of from where you have to count the characters simply maintain a variable that stores the first index of a substring with unique characters(like 'p' that I have used in the code below). Here is my implementation of the above:

int lengthOfLongestSubstring(string s) {
    unordered_map<char, int> mp;
    int n = (int)s.length();
    if(n == 0){
        return 0;
    }
    int res = 1;
    int p = 0;
    mp[s[0]] = 0;
    for(int i = 1; i < n ; i++){

        if(mp.find(s[i]) == mp.end()){
            res = max(res, i-p+1);
            mp[s[i]] = i;
        }
        else{
            char ch = s[i];
            int temp = mp[ch];
            if(p <= temp)
                p = temp + 1;
            res = max(res, i - p + 1);
            mp[ch] = i;
        }

    }
    return res;

}

Try this, it should work.

Upvotes: 2

Related Questions