C++ O(n) in-place 4ms


  • 0
    R
    class Solution {
    public:
        string removeDuplicateLetters(string s) 
        {
            int count[256] = {0};
            for (char c : s)
            {
              ++count[c]; 
            }
            
            int seen[256] = {0};
            size_t save_point{0}, new_size{0};
     
            for ( char c : s)
            {
                //skip dead elements
                if ( ! count[c])  continue; 
                 
                //force ascending order
                if ( ! seen[c] )  
                {
                    while ( new_size > save_point && c < s[new_size-1]) 
                    {
                        seen[s[new_size-1]] = 0;
                        --new_size; 
                    }
                    s[new_size++] = c;
                    seen[c] = 1;
                }
                // append to result
                if (--count[c]==0) 
                {
                    do {
                        count[s[save_point++]] = 0; 
                    }
                    while (new_size > save_point && s[save_point] <= c);
                }
             
            }       
            s.resize(new_size);
            return s;
        }
    };

  • 0

    Could you explain how is it O(n)? Doesn't backtracking to force ascending order introduce additional complexity? Like O(nk) worst case, where k is the number of unique characters.


  • 0

    Never mind, I figured it out. Since backtracking happens at most once for each character, it all boils down to the maximum of 2n operations which is O(n).


Log in to reply
 

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