-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathConstruct String With Repeat Limit
69 lines (68 loc) · 1.76 KB
/
Construct String With Repeat Limit
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
class Solution {
public:
int searchForCharacter(vector<int>v,int i){
for(;;i--){
if(i<0){
return -1;
}
if(v[i]>0){
return i;
}
}
}
string repeatLimitedString(string s, int repeatLimit) {
vector<int>v(26,0);
for(auto x:s){
++v[int(x)-'a'];
}
int i=25,prev=0;
string str="";
int j=25,count=0;
i = searchForCharacter(v,i);
j = i;
while(1){
if(v[i]>0 && count<repeatLimit){
str.push_back(char(i+int('a')));
--v[i];count++;
continue;
}
if(v[i]<=0){
if(i==j){
i = searchForCharacter(v,i-1);
j = i;
if(i<0){
return str;
}
count=0;
continue;
}else{
if(j<0){
return str;
}else{
i=j;
count=0;
continue;
}
}
}
if(count>=repeatLimit){
if(i!=j && j>=0){
if(v[j]>0){
str.push_back(char(j+int('a')));
--v[j];
count=0;
continue;
}
}
j = searchForCharacter(v,j-1);
if(j<0){
return str;
}
str.push_back(char(j+int('a')));
--v[j];
count=0;
}
}
return str;
}
};