C++ O(n^2) solution


  • 0
    J
    class Solution {
    public:
    	int getLength(string s, int k) {
    		int chars[26] = { 0, };
    		for (int i = 0; i < s.length(); i++)
    			chars[s[i] - 'a']++;
    
    		vector<int> nums(s.length(), 0);
    		for (int i = 0; i < s.length(); i++)
    			nums[i] = chars[s[i] - 'a'];
    
    		int result = 0;
    		int res = 0;
    		for (int i = 0; i < s.length(); i++) {
    			if (nums[i] >= k) {
    				res++;
    				result = max(res, result);
    			}
    			else
    				res = 0;
    		}
    
    		return result;
    	}
    
    	int longestSubstring(string s, int k) {
    		int result = 0;
    		int chars[26] = { 0, };
    		for (int i = 0; i < s.length(); i++) 
    			chars[s[i] - 'a']++;
    
    		unordered_set<char> uset;
    		for (int i = 0; i < 26; i++) {
    			if (chars[i] < k && chars[i] > 0)
    				uset.insert(i + 'a');
    		}
    
    		if (uset.empty())
    			return s.length();
    
    		string t = "";
    		for (int i = 0; i < s.length(); i++) {			
    			if (uset.count(s[i]) > 0) {
    				if (t != "") {
    					result = max(result, getLength(t, k));
    					t = "";
    				}
    			}
    			else {
    				t += string(1, s[i]);
    			}
    		}
    
    		if(t.length() > k) {
    			result = max(result, getLength(t, k));
    		}
    
    		return result;
    	}
    };
    

  • 0
    Q

    copy-pasted your code on OJ, and get wrong answer on this test case:
    "ababacb"
    3

    1
    Expected:
    0


  • 0
    J

    You're right. Thank you for pointing out my mistake. I revised my solution and it works well with the test cases.

    class Solution {
    public:
    	int longestSubstring(string s, int k) {
    		if (s.length() < k)
    			return 0;
    
    		int result = s.length();
    		int chars[26] = { 0, };
    		for (int i = 0; i < s.length(); i++) 
    			chars[s[i] - 'a']++;
    
    		int i = 0;
    		while (i < s.length() && chars[s[i] - 'a'] >= k) 
    			i++;
    
    		if (i == s.length())
    			return s.length();
    
    		return max(longestSubstring(s.substr(0, i), k), longestSubstring(s.substr(i + 1), k));
    	}
    };
    

  • 0
    L

    @jaewoo Can you explain why this is O(n)?


  • 0
    J

    @leogogogo After revised my first code, the complexity now is O(n^2). Thank you for your comment and I changed the title.


Log in to reply
 

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