how do I understand the specific solution to one problem in hackerrank？
0
It's about a solution to one problem in hackerrand. please click the link:
the link of problem description
string reverseShuffleMerge(string s) {
int n = s.length();
vector<char> sarr(s.rbegin(), s.rend());
int alpha_size = 26;
vector<int> freq(alpha_size, 0);
for (int i = 0; i < n; i++) {
freq[sarr[i] - 'a']++;
}
vector<int> did_use(alpha_size, 0);
vector<int> can_use(freq.begin(), freq.end());
vector<char> A;
for (int i = 0; i < n; i++) {
if (did_use[sarr[i] - 'a'] < freq[sarr[i] - 'a'] / 2) {
while (A.size() > 0 && sarr[i] < A.back()
&& did_use[A.back() - 'a'] + can_use[A.back() - 'a'] - 1
>= freq[A.back() - 'a'] / 2) {
did_use[A.back() - 'a']--;
A.pop_back();
}
A.push_back(sarr[i]);
did_use[sarr[i] - 'a']++;
can_use[sarr[i] - 'a']--;
} else {
can_use[sarr[i] - 'a']--;
}
}
return string(A.begin(), A.end());
}
I don't get the point of this line: did_use[A.back() - 'a'] + can_use[A.back() - 'a'] - 1 >= freq[A.back() - 'a'] / 2
Could anyone help to shed some light on what part this line plays in the solution?
algorithm
edited Nov 20 '18 at 10:18
gsamaras
50.6k2399186
asked Nov 20 '18 at 10:16
kenneth.sun
42
add a comment |
0
It's about a solution to one problem in hackerrand. please click the link:
the link of problem description
string reverseShuffleMerge(string s) {
int n = s.length();
vector<char> sarr(s.rbegin(), s.rend());
int alpha_size = 26;
vector<int> freq(alpha_size, 0);
for (int i = 0; i < n; i++) {
freq[sarr[i] - 'a']++;
}
vector<int> did_use(alpha_size, 0);
vector<int> can_use(freq.begin(), freq.end());
vector<char> A;
for (int i = 0; i < n; i++) {
if (did_use[sarr[i] - 'a'] < freq[sarr[i] - 'a'] / 2) {
while (A.size() > 0 && sarr[i] < A.back()
&& did_use[A.back() - 'a'] + can_use[A.back() - 'a'] - 1
>= freq[A.back() - 'a'] / 2) {
did_use[A.back() - 'a']--;
A.pop_back();
}
A.push_back(sarr[i]);
did_use[sarr[i] - 'a']++;
can_use[sarr[i] - 'a']--;
} else {
can_use[sarr[i] - 'a']--;
}
}
return string(A.begin(), A.end());
}
I don't get the point of this line: did_use[A.back() - 'a'] + can_use[A.back() - 'a'] - 1 >= freq[A.back() - 'a'] / 2
Could anyone help to shed some light on what part this line plays in the solution?
algorithm
edited Nov 20 '18 at 10:18
gsamaras
50.6k2399186
asked Nov 20 '18 at 10:16
kenneth.sun
42
add a comment |
0
0
0
It's about a solution to one problem in hackerrand. please click the link:
the link of problem description
string reverseShuffleMerge(string s) {
int n = s.length();
vector<char> sarr(s.rbegin(), s.rend());
int alpha_size = 26;
vector<int> freq(alpha_size, 0);
for (int i = 0; i < n; i++) {
freq[sarr[i] - 'a']++;
}
vector<int> did_use(alpha_size, 0);
vector<int> can_use(freq.begin(), freq.end());
vector<char> A;
for (int i = 0; i < n; i++) {
if (did_use[sarr[i] - 'a'] < freq[sarr[i] - 'a'] / 2) {
while (A.size() > 0 && sarr[i] < A.back()
&& did_use[A.back() - 'a'] + can_use[A.back() - 'a'] - 1
>= freq[A.back() - 'a'] / 2) {
did_use[A.back() - 'a']--;
A.pop_back();
}
A.push_back(sarr[i]);
did_use[sarr[i] - 'a']++;
can_use[sarr[i] - 'a']--;
} else {
can_use[sarr[i] - 'a']--;
}
}
return string(A.begin(), A.end());
}
I don't get the point of this line: did_use[A.back() - 'a'] + can_use[A.back() - 'a'] - 1 >= freq[A.back() - 'a'] / 2
Could anyone help to shed some light on what part this line plays in the solution?
algorithm
edited Nov 20 '18 at 10:18
gsamaras
50.6k2399186
asked Nov 20 '18 at 10:16
kenneth.sun
42
It's about a solution to one problem in hackerrand. please click the link:
the link of problem description
string reverseShuffleMerge(string s) {
int n = s.length();
vector<char> sarr(s.rbegin(), s.rend());
int alpha_size = 26;
vector<int> freq(alpha_size, 0);
for (int i = 0; i < n; i++) {
freq[sarr[i] - 'a']++;
}
vector<int> did_use(alpha_size, 0);
vector<int> can_use(freq.begin(), freq.end());
vector<char> A;
for (int i = 0; i < n; i++) {
if (did_use[sarr[i] - 'a'] < freq[sarr[i] - 'a'] / 2) {
while (A.size() > 0 && sarr[i] < A.back()
&& did_use[A.back() - 'a'] + can_use[A.back() - 'a'] - 1
>= freq[A.back() - 'a'] / 2) {
did_use[A.back() - 'a']--;
A.pop_back();
}
A.push_back(sarr[i]);
did_use[sarr[i] - 'a']++;
can_use[sarr[i] - 'a']--;
} else {
can_use[sarr[i] - 'a']--;
}
}
return string(A.begin(), A.end());
}
I don't get the point of this line: did_use[A.back() - 'a'] + can_use[A.back() - 'a'] - 1 >= freq[A.back() - 'a'] / 2
Could anyone help to shed some light on what part this line plays in the solution?
algorithm
algorithm
edited Nov 20 '18 at 10:18
gsamaras
50.6k2399186
asked Nov 20 '18 at 10:16
kenneth.sun
42
edited Nov 20 '18 at 10:18
gsamaras
50.6k2399186
asked Nov 20 '18 at 10:16
kenneth.sun
42
edited Nov 20 '18 at 10:18
gsamaras
50.6k2399186
edited Nov 20 '18 at 10:18
gsamaras
50.6k2399186
edited Nov 20 '18 at 10:18
gsamaras
50.6k2399186
50.6k2399186
asked Nov 20 '18 at 10:16
kenneth.sun
42
asked Nov 20 '18 at 10:16
kenneth.sun
42
asked Nov 20 '18 at 10:16
kenneth.sun
42
42
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
0
In this problem, frequency of all the character in string s will be even number. The answer will contain half of these characters. For example if s="aaaabbcc", then answer must contain 2 a, 1 b and 1 c.
So did_use[A.back() - 'a'] + can_use[A.back() - 'a'] - 1 >= freq[A.back() - 'a'] / 2 this is for if we remove A.back() character, can we add/make required number of A.back() character in later with the remaining string.
answered Nov 20 '18 at 12:16
nightfury1204
1,43048
but why - 1 is needed?
– kenneth.sun
Nov 20 '18 at 13:28
did_use[A.back() - 'a']contains the number of characterA.back()already used,can_use[A.back() - 'a']contains the number of characterA.back()remaining. Since we are trying to remove already added characterA.back()from answer, so if we remove it, number of already used characterA.back()will bedid_use[A.back() - 'a'] - 1.
– nightfury1204
Nov 20 '18 at 13:37
but that is done with did_use[A.back() - 'a']--, isn't that? i still don't understand did_use[A.back() - 'a'] + can_use[A.back() - 'a'] - 1 >= freq[A.back() - 'a'] / 2 well.
– kenneth.sun
Nov 20 '18 at 14:16
that is done with did_use[A.back() - 'a']--, that's right. but first you need to check can you remove the character? that's whydid_use[A.back() - 'a'] + can_use[A.back() - 'a'] - 1 >= freq[A.back() - 'a'] / 2condition is given.
– nightfury1204
Nov 20 '18 at 14:23
i know we need to remove the already added char in this situation. but i have no clue why we have to -1 in did_use[A.back() - 'a'] + can_use[A.back() - 'a'] - 1 >= freq[A.back() - 'a'] / 2 when we want to check if the char can be removed.
– kenneth.sun
Nov 21 '18 at 7:23
|
show 4 more comments
Your Answer
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
draft saved
draft discarded
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53390755%2fhow-do-i-understand-the-specific-solution-to-one-problem-in-hackerrank%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
0
In this problem, frequency of all the character in string s will be even number. The answer will contain half of these characters. For example if s="aaaabbcc", then answer must contain 2 a, 1 b and 1 c.
So did_use[A.back() - 'a'] + can_use[A.back() - 'a'] - 1 >= freq[A.back() - 'a'] / 2 this is for if we remove A.back() character, can we add/make required number of A.back() character in later with the remaining string.
answered Nov 20 '18 at 12:16
nightfury1204
1,43048
but why - 1 is needed?
– kenneth.sun
Nov 20 '18 at 13:28
did_use[A.back() - 'a']contains the number of characterA.back()already used,can_use[A.back() - 'a']contains the number of characterA.back()remaining. Since we are trying to remove already added characterA.back()from answer, so if we remove it, number of already used characterA.back()will bedid_use[A.back() - 'a'] - 1.
– nightfury1204
Nov 20 '18 at 13:37
but that is done with did_use[A.back() - 'a']--, isn't that? i still don't understand did_use[A.back() - 'a'] + can_use[A.back() - 'a'] - 1 >= freq[A.back() - 'a'] / 2 well.
– kenneth.sun
Nov 20 '18 at 14:16
that is done with did_use[A.back() - 'a']--, that's right. but first you need to check can you remove the character? that's whydid_use[A.back() - 'a'] + can_use[A.back() - 'a'] - 1 >= freq[A.back() - 'a'] / 2condition is given.
– nightfury1204
Nov 20 '18 at 14:23
i know we need to remove the already added char in this situation. but i have no clue why we have to -1 in did_use[A.back() - 'a'] + can_use[A.back() - 'a'] - 1 >= freq[A.back() - 'a'] / 2 when we want to check if the char can be removed.
– kenneth.sun
Nov 21 '18 at 7:23
|
show 4 more comments
0
In this problem, frequency of all the character in string s will be even number. The answer will contain half of these characters. For example if s="aaaabbcc", then answer must contain 2 a, 1 b and 1 c.
So did_use[A.back() - 'a'] + can_use[A.back() - 'a'] - 1 >= freq[A.back() - 'a'] / 2 this is for if we remove A.back() character, can we add/make required number of A.back() character in later with the remaining string.
answered Nov 20 '18 at 12:16
nightfury1204
1,43048
but why - 1 is needed?
– kenneth.sun
Nov 20 '18 at 13:28
did_use[A.back() - 'a']contains the number of characterA.back()already used,can_use[A.back() - 'a']contains the number of characterA.back()remaining. Since we are trying to remove already added characterA.back()from answer, so if we remove it, number of already used characterA.back()will bedid_use[A.back() - 'a'] - 1.
– nightfury1204
Nov 20 '18 at 13:37
but that is done with did_use[A.back() - 'a']--, isn't that? i still don't understand did_use[A.back() - 'a'] + can_use[A.back() - 'a'] - 1 >= freq[A.back() - 'a'] / 2 well.
– kenneth.sun
Nov 20 '18 at 14:16
that is done with did_use[A.back() - 'a']--, that's right. but first you need to check can you remove the character? that's whydid_use[A.back() - 'a'] + can_use[A.back() - 'a'] - 1 >= freq[A.back() - 'a'] / 2condition is given.
– nightfury1204
Nov 20 '18 at 14:23
i know we need to remove the already added char in this situation. but i have no clue why we have to -1 in did_use[A.back() - 'a'] + can_use[A.back() - 'a'] - 1 >= freq[A.back() - 'a'] / 2 when we want to check if the char can be removed.
– kenneth.sun
Nov 21 '18 at 7:23
|
show 4 more comments
0
0
0
In this problem, frequency of all the character in string s will be even number. The answer will contain half of these characters. For example if s="aaaabbcc", then answer must contain 2 a, 1 b and 1 c.
So did_use[A.back() - 'a'] + can_use[A.back() - 'a'] - 1 >= freq[A.back() - 'a'] / 2 this is for if we remove A.back() character, can we add/make required number of A.back() character in later with the remaining string.
answered Nov 20 '18 at 12:16
nightfury1204
1,43048
In this problem, frequency of all the character in string s will be even number. The answer will contain half of these characters. For example if s="aaaabbcc", then answer must contain 2 a, 1 b and 1 c.
So did_use[A.back() - 'a'] + can_use[A.back() - 'a'] - 1 >= freq[A.back() - 'a'] / 2 this is for if we remove A.back() character, can we add/make required number of A.back() character in later with the remaining string.
answered Nov 20 '18 at 12:16
nightfury1204
1,43048
answered Nov 20 '18 at 12:16
nightfury1204
1,43048
answered Nov 20 '18 at 12:16
nightfury1204
1,43048
answered Nov 20 '18 at 12:16
nightfury1204
1,43048
1,43048
but why - 1 is needed?
– kenneth.sun
Nov 20 '18 at 13:28
did_use[A.back() - 'a']contains the number of characterA.back()already used,can_use[A.back() - 'a']contains the number of characterA.back()remaining. Since we are trying to remove already added characterA.back()from answer, so if we remove it, number of already used characterA.back()will bedid_use[A.back() - 'a'] - 1.
– nightfury1204
Nov 20 '18 at 13:37
but that is done with did_use[A.back() - 'a']--, isn't that? i still don't understand did_use[A.back() - 'a'] + can_use[A.back() - 'a'] - 1 >= freq[A.back() - 'a'] / 2 well.
– kenneth.sun
Nov 20 '18 at 14:16
that is done with did_use[A.back() - 'a']--, that's right. but first you need to check can you remove the character? that's whydid_use[A.back() - 'a'] + can_use[A.back() - 'a'] - 1 >= freq[A.back() - 'a'] / 2condition is given.
– nightfury1204
Nov 20 '18 at 14:23
i know we need to remove the already added char in this situation. but i have no clue why we have to -1 in did_use[A.back() - 'a'] + can_use[A.back() - 'a'] - 1 >= freq[A.back() - 'a'] / 2 when we want to check if the char can be removed.
– kenneth.sun
Nov 21 '18 at 7:23
|
show 4 more comments
but why - 1 is needed?
– kenneth.sun
Nov 20 '18 at 13:28
did_use[A.back() - 'a']contains the number of characterA.back()already used,can_use[A.back() - 'a']contains the number of characterA.back()remaining. Since we are trying to remove already added characterA.back()from answer, so if we remove it, number of already used characterA.back()will bedid_use[A.back() - 'a'] - 1.
– nightfury1204
Nov 20 '18 at 13:37
but that is done with did_use[A.back() - 'a']--, isn't that? i still don't understand did_use[A.back() - 'a'] + can_use[A.back() - 'a'] - 1 >= freq[A.back() - 'a'] / 2 well.
– kenneth.sun
Nov 20 '18 at 14:16
that is done with did_use[A.back() - 'a']--, that's right. but first you need to check can you remove the character? that's whydid_use[A.back() - 'a'] + can_use[A.back() - 'a'] - 1 >= freq[A.back() - 'a'] / 2condition is given.
– nightfury1204
Nov 20 '18 at 14:23
i know we need to remove the already added char in this situation. but i have no clue why we have to -1 in did_use[A.back() - 'a'] + can_use[A.back() - 'a'] - 1 >= freq[A.back() - 'a'] / 2 when we want to check if the char can be removed.
– kenneth.sun
Nov 21 '18 at 7:23
but why - 1 is needed?
– kenneth.sun
Nov 20 '18 at 13:28
but why - 1 is needed?
– kenneth.sun
Nov 20 '18 at 13:28
did_use[A.back() - 'a'] contains the number of character A.back() already used, can_use[A.back() - 'a'] contains the number of character A.back() remaining. Since we are trying to remove already added character A.back() from answer, so if we remove it, number of already used character A.back() will be did_use[A.back() - 'a'] - 1.– nightfury1204
Nov 20 '18 at 13:37
did_use[A.back() - 'a'] contains the number of character A.back() already used, can_use[A.back() - 'a'] contains the number of character A.back() remaining. Since we are trying to remove already added character A.back() from answer, so if we remove it, number of already used character A.back() will be did_use[A.back() - 'a'] - 1.– nightfury1204
Nov 20 '18 at 13:37
but that is done with did_use[A.back() - 'a']--, isn't that? i still don't understand did_use[A.back() - 'a'] + can_use[A.back() - 'a'] - 1 >= freq[A.back() - 'a'] / 2 well.
– kenneth.sun
Nov 20 '18 at 14:16
but that is done with did_use[A.back() - 'a']--, isn't that? i still don't understand did_use[A.back() - 'a'] + can_use[A.back() - 'a'] - 1 >= freq[A.back() - 'a'] / 2 well.
– kenneth.sun
Nov 20 '18 at 14:16
that is done with did_use[A.back() - 'a']--, that's right. but first you need to check can you remove the character? that's why
did_use[A.back() - 'a'] + can_use[A.back() - 'a'] - 1 >= freq[A.back() - 'a'] / 2 condition is given.– nightfury1204
Nov 20 '18 at 14:23
that is done with did_use[A.back() - 'a']--, that's right. but first you need to check can you remove the character? that's why
did_use[A.back() - 'a'] + can_use[A.back() - 'a'] - 1 >= freq[A.back() - 'a'] / 2 condition is given.– nightfury1204
Nov 20 '18 at 14:23
i know we need to remove the already added char in this situation. but i have no clue why we have to -1 in did_use[A.back() - 'a'] + can_use[A.back() - 'a'] - 1 >= freq[A.back() - 'a'] / 2 when we want to check if the char can be removed.
– kenneth.sun
Nov 21 '18 at 7:23
i know we need to remove the already added char in this situation. but i have no clue why we have to -1 in did_use[A.back() - 'a'] + can_use[A.back() - 'a'] - 1 >= freq[A.back() - 'a'] / 2 when we want to check if the char can be removed.
– kenneth.sun
Nov 21 '18 at 7:23
|
show 4 more comments
draft saved
draft discarded
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
draft saved
draft discarded
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53390755%2fhow-do-i-understand-the-specific-solution-to-one-problem-in-hackerrank%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
