4-liner C++ O(N) greedy method in two versions (detailed explanation)


  • 1

    For coding convenience, we pre-process the secrete signature string s by s += 'I'. Now s can be partitioned into several disjoint segments in format

    • s = [D...DI] + [D...DI] + ... [D...DI],

    where each segment [D...DI] represents a decreasing subsequence in [1, n] and there must be a "jump" from one segment to next. Note that there may be zero D's in a segment (e.g., [I]).

    With greedy method, we can create the lexicographically smallest valid sequence:

    1. For first segment D...DI (length = L), pick L smallest numbers from initial range [1, n] and push into result vector res in decreasing order;
    2. Remove those L numbers from range [1, n];
    3. Go to next segment and repeat steps 1 and 2 until exhausting entire string s.
        vector<int> findPermutation(string s) {
          vector<int> res; s += 'I';
          for (int i = 0; i < s.size(); i = res.size())
            for (int j=s.find('I',i)+1; j > i; res.push_back(j--)) ;
          return res;
        }
    

    Alternatively, we can also use std::reverse in a single loop:

        vector<int> findPermutation(string s) {
          vector<int> res((s += 'I').size());
          for (int i = 0, j = 0; i < s.size() && (res[i] = ++i); )
            if (s[i-1] == 'I') reverse(res.begin()+j, res.begin()+i), j = i;
    
          return res;
        }
    

Log in to reply
 

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