I Post My O(n^2) Solution Here(It luckily got accepted). Anybody has an O(n) solution?


  • 0
    S
    class Solution {
    public:
        int lengthOfLongestSubstring(string s) {
            unordered_set<char> table;
            int tmpCnt = 0;
            int maxCnt = 0;
            for(int i = 0; i < s.length(); i++){
                auto iter = table.find(s[i]);
                if(iter == table.end()){
                    tmpCnt++;
                }
                else{
                    table.clear();
                    tmpCnt = 1;
                    int j = i-1;
                    while(s[j]!=s[i]){
                        table.emplace(s[j]);
                        j--; tmpCnt++;
                    }
                }
                table.emplace(s[i]);
                if(tmpCnt > maxCnt) maxCnt = tmpCnt;
            }
            return maxCnt;
        }
    };
    

    I tried to use a Unordered_set to keep track of the previous char I encountered. When I encounter a char that has previously appeared, I will firstly clear the content of the unordered_set, then push all the char behind the char that appeared twice back into the unordered_set. At the meantime, I am storing my counting result to a counter variable and finally use this variable to update my 'max' value.

    But I am feeling terrible about this O(n^2) method. It would be great if you guys can give me some inspiration on a O(n) method.


  • 1

    Your algorithm's runtime complexity is in fact O(n) and not O(n2). In your code, the number of iteration is in the order of m x n, where m is the number of unique characters that could contain in s. Since the number of unique ascii characters is constant (m = 255), the complexity boils down to the order of O(n).

    That being said, there exists a more efficient O(n) algorithm which does at most 2n iterations. You can read about the in-depth analysis I wrote here.

    Side note:
    I have improved the test case such that your code is judged as Time Limit Exceeded now.


  • 0
    S

    Hey man thanks for your kind reply! I was one step further for your proposed answer. Recording start point and end point of the substring using two variables was something I should definitely go through my mind.


  • 0
    S

    LOL for the new test case. it is destructive


  • 0
    R
    This post is deleted!

  • 0
    K
    This post is deleted!

  • 0
    S

    Thanks for your post. However it would better to post as answer with more detail content. Please read the FAQ (http://oj.leetcode.com/discuss/faq) for more info.


  • 0
    S

    Thanks for your post. However it would better to post as answer with more detail content. Please read the FAQ (http://oj.leetcode.com/discuss/faq) for more info.


  • 0
    R
    class Solution {
    public:
        int lengthOfLongestSubstring(string s) {
            int arr[256]={0};
            int k = s.length();
            int start=0,count=0,max=0,i;
            for(i=0;i<s.length();i++)
            {  
                if(arr[s[i]]&&arr[s[i]]>=start )
                {
                    start=arr[s[i]];
                    count=i-start+1;
                    arr[s[i]]=i+1;
                }
    
                else
                {
                    arr[s[i]]=i+1;
                    ++count;
                }
    
    
              if(count>max)
                 max=count;
    
      }
            return max;
        }
    };
    

    its a O(n) solution which determines the answer in single pass.
    m using a char buffer to store the index of the characters in the current substring,
    if the current character is already present in the current substring, we start a new substring.

    we update 'start' of a new substring
    as previous index of the current character + 1


  • 0
    I
    class Solution {
    public:
    	int lengthOfLongestSubstring(string s) {
    		int count(0), index(0), res(0);
    		unordered_map<char, int> dup;
    		for (int i = 0; i < s.length(); i++){
    			if (dup.count(s[i])&&dup[s[i]]>=index){
    				index = dup[s[i]];
    				count = i - index - 1;
    			}
    			dup[s[i]] = i;
    			count++;
    			res = std::max(res, count);
    		}
    		return res;
    	}
    };
    

    I use a int index to record last repeated char's position.


Log in to reply
 

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