-
Notifications
You must be signed in to change notification settings - Fork 77
/
ReverseShuffleMerge.js
80 lines (66 loc) · 1.72 KB
/
ReverseShuffleMerge.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
'use strict';
const fs = require('fs');
process.stdin.resume();
process.stdin.setEncoding('utf-8');
let inputString = '';
let currentLine = 0;
process.stdin.on('data', inputStdin => {
inputString += inputStdin;
});
process.stdin.on('end', _ => {
inputString = inputString.replace(/\s*$/, '')
.split('\n')
.map(str => str.replace(/\s*$/, ''));
main();
});
function readLine() {
return inputString[currentLine++];
}
// Complete the reverseShuffleMerge function below.
function reverseShuffleMerge(s) {
let map={};
s = s.split('').reverse('').join('')
for(let item of s.split('')){
map[item]=map[item]?map[item]+1:1;
}
let ref={}
for(let key in map){
ref[key] = map[key]/2
}
let solution = [],i=0;
while (solution.length<s.length/2){
let min_char_pos = -1
//find the smallest
//find the smallest
//find the smallest
while(true){
let c=s[i];
if(ref[c]>0&&(min_char_pos<0||c<s[min_char_pos])){
min_char_pos = i;
}
map[c] -= 1;
if(map[c] < ref[c]){
break
}
i+=1
}
//found the one, restore the count of other
for(let j=min_char_pos+1;j<i+1;j++){
map[s[j]]+=1
}
//find the smallest
//find the smallest
//find the smallest
ref[s[min_char_pos]]-=1
solution.push(s[min_char_pos]);
i= min_char_pos+1
}
return solution.join('');
}
function main() {
const ws = fs.createWriteStream(process.env.OUTPUT_PATH);
const s = readLine();
let result = reverseShuffleMerge(s);
ws.write(result + "\n");
ws.end();
}