767. Reorganize String

01//priority queue
02//Runtime: 12 ms, faster than 13.62% of C++ online submissions for Reorganize String.
03//Memory Usage: 6.4 MB, less than 100.00% of C++ online submissions for Reorganize String.
04class Solution {
05public:
06    string reorganizeString(string S) {
07        unordered_map<char, int> counter;
08        
09        for(char c : S){
10            counter[c]++;
11        }
12        
13        auto comp = [](const pair<char, int>& a, const pair<char, int>& b){
14            return (a.second == b.second) ? (a.first > b.first) : a.second < b.second;};
15        
16        //the larger count, the earlier be popped
17        //the smaller char order, the earlier be popped
18        priority_queue<pair<char, int>, vector<pair<char, int>>, decltype(comp)> pq(comp);
19        
20        for(auto it = counter.begin(); it != counter.end(); it++){
21            pq.push(make_pair(it->first, it->second));
22        }
23        
24        string ans = "";
25        
26        while(!pq.empty()){
27            //pop two elements at a time
28            pair<char, int> cur = pq.top(); pq.pop();
29            pair<char, int> next = make_pair(' ', 0);
30            
31            // cout << cur.first << " " << cur.second << endl;
32            
33            if(pq.size() > 0){
34                next = pq.top(); pq.pop();
35                cout << next.first << " " << next.second << endl;
36            }
37            
38            cur.second--;
39            if(ans.size() > 0 && cur.first == ans[ans.size()-1]) return "";
40            ans += cur.first;
41            
42            if(next.first != ' '){
43                next.second--;
44                if(ans.size() > 0 && next.first == ans[ans.size()-1]) return "";
45                ans += next.first;
46            }
47            
48            //push them back to the queue
49            if(cur.second > 0){
50                pq.push(cur);
51            }
52            
53            if(next.second > 0){
54                pq.push(next);
55            }
56        }
57        
58        return ans;
59    }
60};
61
62//Approach #1: Sort by Count
63//Runtime: 0 ms, faster than 100.00% of C++ online submissions for Reorganize String.
64//Memory Usage: 6.2 MB, less than 100.00% of C++ online submissions for Reorganize String.
65//A: size of the alphabet, N: ength of S
66//time: O(AN + AlogA), space: O(N)
67class Solution {
68public:
69    string reorganizeString(string S) {
70        int N = S.size();
71        //a hash calculated by count and its lexicographic order
72        vector<int> countLex(26, 0);
73        
74        //count part
75        for(char c: S){
76            countLex[c-'a'] += 26;
77        }
78        //lexicographic part
79        for(int i = 0; i < 26; i++){
80            countLex[i] += i;
81        }
82        
83        //we start from the char with smaller count
84        sort(countLex.begin(), countLex.end());
85        
86        vector<char> ans(N);
87        int cursor = 1;
88        for(int code : countLex){
89            int count = code/26;
90            char c = 'a' + (code%26);
91            /*
92            if S's length is 3, a character cannot appear more than 2 times
93            if S's length is 4, a character cannot appear more than 2 times
94            */
95            if(count > (N+1)/2) return "";
96            for(int i = 0; i < count; i++){
97                /*
98                the latter char(char with larger count) will start from 0
99                for example, in "abaca", 'a' is processed at last, 
100                and it will fill 0,2,4th position
101                */
102                if(cursor >= N) cursor = 0;
103                // cout << cursor << " " << c << endl;
104                ans[cursor] = c;
105                //jump to next next position
106                cursor += 2;
107            }
108        }
109        
110        return string(ans.begin(), ans.end());
111    }
112};
113
114//Approach #2: Greedy with Heap
115//priority queue, process two char at a time
116//Runtime: 4 ms, faster than 64.77% of C++ online submissions for Reorganize String.
117//Memory Usage: 6.6 MB, less than 100.00% of C++ online submissions for Reorganize String.
118//time: O(NlogA), space: O(A)
119class Solution {
120public:
121    string reorganizeString(string S) {
122        int N = S.size();
123        unordered_map<char, int> counter;
124        
125        for(char c : S){
126            counter[c]++;
127        }
128        
129        auto comp = [](const pair<char, int>& a, const pair<char, int>& b){
130            return (a.second == b.second) ? (a.first > b.first) : a.second < b.second;};
131        
132        //the larger count, the earlier be popped
133        //the smaller char order, the earlier be popped
134        priority_queue<pair<char, int>, vector<pair<char, int>>, decltype(comp)> pq(comp);
135        
136        for(auto it = counter.begin(); it != counter.end(); it++){
137            //early stopping
138            if(it->second > (N+1)/2) return "";
139            pq.push(make_pair(it->first, it->second));
140        }
141        
142        string ans = "";
143        
144        while(pq.size() >= 2){
145            //pop two elements at a time
146            pair<char, int> cur = pq.top(); pq.pop();
147            pair<char, int> next = pq.top(); pq.pop();
148            
149            //we don't need this check now, because we process two different char at one time 
150            // if(ans.size() > 0 && cur.first == ans[ans.size()-1]) return "";
151            ans += cur.first;
152            
153            // if(ans.size() > 0 && next.first == ans[ans.size()-1]) return "";
154            ans += next.first;
155            
156            //push them back to the queue
157            if(--cur.second > 0) pq.push(cur);
158            if(--next.second > 0) pq.push(next);
159        }
160        
161        //we jump out the loop when its size is 0 or 1
162        if(!pq.empty()) ans += pq.top().first;
163        
164        return ans;
165    }
166};