Concatenate words in such a way as to obtain the longest possible sub-string of the same letter
$begingroup$
An array of N words is given. Each word consists of small letters
('a'- 'z'). Our goal is to concatenate the words in such a way as to
obtain a single word with the longest possible sub-string composed of
one particular letter. Find the length of such a sub-string.
- Examples:
- Given N=3 and words=['aabb','aaaa','bbab'], your function should return 6. One of the best concatenations is
words[1]+words[0]+words[2]='aaaaaabbbbab'. The longest sub-string is
composed of the letter 'a' and its length is 6. - Given N=3 and words=['xxbxx','xbx','x'], your function should return 4. One of the best concatenations is
words[0]+words[2]+words[1]='xxbxxxxbx'. The longest sub-string is
composed of letter 'x' and its length is 4.
- Given N=3 and words=['aabb','aaaa','bbab'], your function should return 6. One of the best concatenations is
public class DailyCodingProblem4 {
public static void main(String args) {
String arr = { "aabb", "aaaa", "bbab" };
int res = solution(arr);
System.out.println(res);
String arr2 = { "xxbxx", "xbx", "x" };
res = solution(arr2);
System.out.println(res);
}
private static int solution(String arr) {
Map<Integer, Integer> prefix = new HashMap<>();
Map<Integer, Integer> suffix = new HashMap<>();
Map<Integer, Integer> both = new HashMap<>();
for (int i = 0; i < arr.length; i++) {
String word = arr[i];
int j = 1;
while (j < word.length() && word.charAt(0) == word.charAt(j)) {
j++;
}
int key = word.charAt(0);
if (j == word.length()) {
if (both.containsKey(key)) {
Integer temp = both.get(key);
both.put(key, j + temp);
} else {
both.put(key, j);
}
} else {
if (suffix.containsKey(key)) {
Integer temp = suffix.get(key);
if (j > temp) {
suffix.put(key, j);
}
} else {
suffix.put(key, j);
}
j = word.length() - 1;
while (j > 0 && word.charAt(word.length() - 1) == word.charAt(j - 1)) {
j--;
}
key = word.charAt(word.length() - 1);
if (prefix.containsKey(key)) {
Integer temp = prefix.get(key);
if (word.length() - j > temp) {
prefix.put(key, word.length() - j);
}
} else {
prefix.put(key, word.length() - j);
}
}
}
int res = 0;
for (Integer key : prefix.keySet()) {
if (suffix.containsKey(key)) {
int temp = prefix.get(key) + suffix.get(key);
if (temp > res) {
res = temp;
}
}
}
for (Integer key : suffix.keySet()) {
if (prefix.containsKey(key)) {
int temp = prefix.get(key) + suffix.get(key);
if (temp > res) {
res = temp;
}
}
}
for (Integer key : both.keySet()) {
if (prefix.containsKey(key)) {
int temp = prefix.get(key) + both.get(key);
if (temp > res) {
res = temp;
}
}
if (suffix.containsKey(key)) {
int temp = both.get(key) + suffix.get(key);
if (temp > res) {
res = temp;
}
}
}
return res;
}
}
Is there a better approach to solve the above problem? Is there something I can improve on?
java algorithm strings programming-challenge
$endgroup$
add a comment |
$begingroup$
An array of N words is given. Each word consists of small letters
('a'- 'z'). Our goal is to concatenate the words in such a way as to
obtain a single word with the longest possible sub-string composed of
one particular letter. Find the length of such a sub-string.
- Examples:
- Given N=3 and words=['aabb','aaaa','bbab'], your function should return 6. One of the best concatenations is
words[1]+words[0]+words[2]='aaaaaabbbbab'. The longest sub-string is
composed of the letter 'a' and its length is 6. - Given N=3 and words=['xxbxx','xbx','x'], your function should return 4. One of the best concatenations is
words[0]+words[2]+words[1]='xxbxxxxbx'. The longest sub-string is
composed of letter 'x' and its length is 4.
- Given N=3 and words=['aabb','aaaa','bbab'], your function should return 6. One of the best concatenations is
public class DailyCodingProblem4 {
public static void main(String args) {
String arr = { "aabb", "aaaa", "bbab" };
int res = solution(arr);
System.out.println(res);
String arr2 = { "xxbxx", "xbx", "x" };
res = solution(arr2);
System.out.println(res);
}
private static int solution(String arr) {
Map<Integer, Integer> prefix = new HashMap<>();
Map<Integer, Integer> suffix = new HashMap<>();
Map<Integer, Integer> both = new HashMap<>();
for (int i = 0; i < arr.length; i++) {
String word = arr[i];
int j = 1;
while (j < word.length() && word.charAt(0) == word.charAt(j)) {
j++;
}
int key = word.charAt(0);
if (j == word.length()) {
if (both.containsKey(key)) {
Integer temp = both.get(key);
both.put(key, j + temp);
} else {
both.put(key, j);
}
} else {
if (suffix.containsKey(key)) {
Integer temp = suffix.get(key);
if (j > temp) {
suffix.put(key, j);
}
} else {
suffix.put(key, j);
}
j = word.length() - 1;
while (j > 0 && word.charAt(word.length() - 1) == word.charAt(j - 1)) {
j--;
}
key = word.charAt(word.length() - 1);
if (prefix.containsKey(key)) {
Integer temp = prefix.get(key);
if (word.length() - j > temp) {
prefix.put(key, word.length() - j);
}
} else {
prefix.put(key, word.length() - j);
}
}
}
int res = 0;
for (Integer key : prefix.keySet()) {
if (suffix.containsKey(key)) {
int temp = prefix.get(key) + suffix.get(key);
if (temp > res) {
res = temp;
}
}
}
for (Integer key : suffix.keySet()) {
if (prefix.containsKey(key)) {
int temp = prefix.get(key) + suffix.get(key);
if (temp > res) {
res = temp;
}
}
}
for (Integer key : both.keySet()) {
if (prefix.containsKey(key)) {
int temp = prefix.get(key) + both.get(key);
if (temp > res) {
res = temp;
}
}
if (suffix.containsKey(key)) {
int temp = both.get(key) + suffix.get(key);
if (temp > res) {
res = temp;
}
}
}
return res;
}
}
Is there a better approach to solve the above problem? Is there something I can improve on?
java algorithm strings programming-challenge
$endgroup$
$begingroup$
Insolution
, your handling for theboth
case appears wrong. If you have words 'aa' and 'aaa', you would not replace the 2 with a 3, but rather you would add the 2+3 getting 5, since you can concatenate the words as 'aaaaa', right?
$endgroup$
– Austin Hastings
1 hour ago
$begingroup$
@AustinHastings you are right. I have missed it.
$endgroup$
– Maclean Pinto
55 mins ago
$begingroup$
@AustinHastings updated line 43 to both.put(key, j + temp); This should solve it.
$endgroup$
– Maclean Pinto
45 mins ago
add a comment |
$begingroup$
An array of N words is given. Each word consists of small letters
('a'- 'z'). Our goal is to concatenate the words in such a way as to
obtain a single word with the longest possible sub-string composed of
one particular letter. Find the length of such a sub-string.
- Examples:
- Given N=3 and words=['aabb','aaaa','bbab'], your function should return 6. One of the best concatenations is
words[1]+words[0]+words[2]='aaaaaabbbbab'. The longest sub-string is
composed of the letter 'a' and its length is 6. - Given N=3 and words=['xxbxx','xbx','x'], your function should return 4. One of the best concatenations is
words[0]+words[2]+words[1]='xxbxxxxbx'. The longest sub-string is
composed of letter 'x' and its length is 4.
- Given N=3 and words=['aabb','aaaa','bbab'], your function should return 6. One of the best concatenations is
public class DailyCodingProblem4 {
public static void main(String args) {
String arr = { "aabb", "aaaa", "bbab" };
int res = solution(arr);
System.out.println(res);
String arr2 = { "xxbxx", "xbx", "x" };
res = solution(arr2);
System.out.println(res);
}
private static int solution(String arr) {
Map<Integer, Integer> prefix = new HashMap<>();
Map<Integer, Integer> suffix = new HashMap<>();
Map<Integer, Integer> both = new HashMap<>();
for (int i = 0; i < arr.length; i++) {
String word = arr[i];
int j = 1;
while (j < word.length() && word.charAt(0) == word.charAt(j)) {
j++;
}
int key = word.charAt(0);
if (j == word.length()) {
if (both.containsKey(key)) {
Integer temp = both.get(key);
both.put(key, j + temp);
} else {
both.put(key, j);
}
} else {
if (suffix.containsKey(key)) {
Integer temp = suffix.get(key);
if (j > temp) {
suffix.put(key, j);
}
} else {
suffix.put(key, j);
}
j = word.length() - 1;
while (j > 0 && word.charAt(word.length() - 1) == word.charAt(j - 1)) {
j--;
}
key = word.charAt(word.length() - 1);
if (prefix.containsKey(key)) {
Integer temp = prefix.get(key);
if (word.length() - j > temp) {
prefix.put(key, word.length() - j);
}
} else {
prefix.put(key, word.length() - j);
}
}
}
int res = 0;
for (Integer key : prefix.keySet()) {
if (suffix.containsKey(key)) {
int temp = prefix.get(key) + suffix.get(key);
if (temp > res) {
res = temp;
}
}
}
for (Integer key : suffix.keySet()) {
if (prefix.containsKey(key)) {
int temp = prefix.get(key) + suffix.get(key);
if (temp > res) {
res = temp;
}
}
}
for (Integer key : both.keySet()) {
if (prefix.containsKey(key)) {
int temp = prefix.get(key) + both.get(key);
if (temp > res) {
res = temp;
}
}
if (suffix.containsKey(key)) {
int temp = both.get(key) + suffix.get(key);
if (temp > res) {
res = temp;
}
}
}
return res;
}
}
Is there a better approach to solve the above problem? Is there something I can improve on?
java algorithm strings programming-challenge
$endgroup$
An array of N words is given. Each word consists of small letters
('a'- 'z'). Our goal is to concatenate the words in such a way as to
obtain a single word with the longest possible sub-string composed of
one particular letter. Find the length of such a sub-string.
- Examples:
- Given N=3 and words=['aabb','aaaa','bbab'], your function should return 6. One of the best concatenations is
words[1]+words[0]+words[2]='aaaaaabbbbab'. The longest sub-string is
composed of the letter 'a' and its length is 6. - Given N=3 and words=['xxbxx','xbx','x'], your function should return 4. One of the best concatenations is
words[0]+words[2]+words[1]='xxbxxxxbx'. The longest sub-string is
composed of letter 'x' and its length is 4.
- Given N=3 and words=['aabb','aaaa','bbab'], your function should return 6. One of the best concatenations is
public class DailyCodingProblem4 {
public static void main(String args) {
String arr = { "aabb", "aaaa", "bbab" };
int res = solution(arr);
System.out.println(res);
String arr2 = { "xxbxx", "xbx", "x" };
res = solution(arr2);
System.out.println(res);
}
private static int solution(String arr) {
Map<Integer, Integer> prefix = new HashMap<>();
Map<Integer, Integer> suffix = new HashMap<>();
Map<Integer, Integer> both = new HashMap<>();
for (int i = 0; i < arr.length; i++) {
String word = arr[i];
int j = 1;
while (j < word.length() && word.charAt(0) == word.charAt(j)) {
j++;
}
int key = word.charAt(0);
if (j == word.length()) {
if (both.containsKey(key)) {
Integer temp = both.get(key);
both.put(key, j + temp);
} else {
both.put(key, j);
}
} else {
if (suffix.containsKey(key)) {
Integer temp = suffix.get(key);
if (j > temp) {
suffix.put(key, j);
}
} else {
suffix.put(key, j);
}
j = word.length() - 1;
while (j > 0 && word.charAt(word.length() - 1) == word.charAt(j - 1)) {
j--;
}
key = word.charAt(word.length() - 1);
if (prefix.containsKey(key)) {
Integer temp = prefix.get(key);
if (word.length() - j > temp) {
prefix.put(key, word.length() - j);
}
} else {
prefix.put(key, word.length() - j);
}
}
}
int res = 0;
for (Integer key : prefix.keySet()) {
if (suffix.containsKey(key)) {
int temp = prefix.get(key) + suffix.get(key);
if (temp > res) {
res = temp;
}
}
}
for (Integer key : suffix.keySet()) {
if (prefix.containsKey(key)) {
int temp = prefix.get(key) + suffix.get(key);
if (temp > res) {
res = temp;
}
}
}
for (Integer key : both.keySet()) {
if (prefix.containsKey(key)) {
int temp = prefix.get(key) + both.get(key);
if (temp > res) {
res = temp;
}
}
if (suffix.containsKey(key)) {
int temp = both.get(key) + suffix.get(key);
if (temp > res) {
res = temp;
}
}
}
return res;
}
}
Is there a better approach to solve the above problem? Is there something I can improve on?
java algorithm strings programming-challenge
java algorithm strings programming-challenge
edited 44 mins ago
Maclean Pinto
asked 1 hour ago
Maclean PintoMaclean Pinto
1395
1395
$begingroup$
Insolution
, your handling for theboth
case appears wrong. If you have words 'aa' and 'aaa', you would not replace the 2 with a 3, but rather you would add the 2+3 getting 5, since you can concatenate the words as 'aaaaa', right?
$endgroup$
– Austin Hastings
1 hour ago
$begingroup$
@AustinHastings you are right. I have missed it.
$endgroup$
– Maclean Pinto
55 mins ago
$begingroup$
@AustinHastings updated line 43 to both.put(key, j + temp); This should solve it.
$endgroup$
– Maclean Pinto
45 mins ago
add a comment |
$begingroup$
Insolution
, your handling for theboth
case appears wrong. If you have words 'aa' and 'aaa', you would not replace the 2 with a 3, but rather you would add the 2+3 getting 5, since you can concatenate the words as 'aaaaa', right?
$endgroup$
– Austin Hastings
1 hour ago
$begingroup$
@AustinHastings you are right. I have missed it.
$endgroup$
– Maclean Pinto
55 mins ago
$begingroup$
@AustinHastings updated line 43 to both.put(key, j + temp); This should solve it.
$endgroup$
– Maclean Pinto
45 mins ago
$begingroup$
In
solution
, your handling for the both
case appears wrong. If you have words 'aa' and 'aaa', you would not replace the 2 with a 3, but rather you would add the 2+3 getting 5, since you can concatenate the words as 'aaaaa', right?$endgroup$
– Austin Hastings
1 hour ago
$begingroup$
In
solution
, your handling for the both
case appears wrong. If you have words 'aa' and 'aaa', you would not replace the 2 with a 3, but rather you would add the 2+3 getting 5, since you can concatenate the words as 'aaaaa', right?$endgroup$
– Austin Hastings
1 hour ago
$begingroup$
@AustinHastings you are right. I have missed it.
$endgroup$
– Maclean Pinto
55 mins ago
$begingroup$
@AustinHastings you are right. I have missed it.
$endgroup$
– Maclean Pinto
55 mins ago
$begingroup$
@AustinHastings updated line 43 to both.put(key, j + temp); This should solve it.
$endgroup$
– Maclean Pinto
45 mins ago
$begingroup$
@AustinHastings updated line 43 to both.put(key, j + temp); This should solve it.
$endgroup$
– Maclean Pinto
45 mins ago
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
I think I see a few bugs:
In the initial processing loop, your handling for the
both
case appears wrong. If you have words 'aa' and 'aaa', you would not replace the 2 with a 3, but rather you would add the 2+3 getting 5, since you can concatenate the words as 'aaaaa'.
In the prefix/suffix handling, there is the possibility that the same word would be the largest prefix and suffix, which is an impossibility. Consider a test case like this:
String arr = { "xxbxxx", "xbx", "x" }; // note: xx(2)bxxx(3)
res = solution(arr);
What should
res
be? I believe you will compute theprefix['x']
as being 3, and thesuffix['x']
as being 2, yielding an answer of 6. But the correct answer is 5, since you cannot use "xxbxxx" twice.
(Note: This is a significant problem, since if true it will require you to significantly change how you are implementing your solution.)
In the final phase, computing results, your
prefix
andsuffix
loops ignore the possibility of a single winner. That is,prefix
requires asuffix
to win, andsuffix
requires aprefix
to win. It does not allow for the possibility that a word like "xzzzzzzzzzz" could have a long enough (prefix|suffix) to just dominate the result.The same is true for
both
: there is no acknowledgement of the possibility of a prefix+both+suffix.
And now here's some non-bug stuff:
You spend a lot of time checking if a map contains a given key. If you go through and count lines of code, it is probably the most expensive thing you do. (Not to mention that many of your bugs are around this area.) I think it would benefit you to set up your maps so that the keys were always present with a default value of zero. There are some proposed options in this SO question.
For a specific example, consider this:
if (both.containsKey(key)) {
Integer temp = both.get(key);
if (j > temp) {
both.put(key, j);
}
} else {
both.put(key, j);
}
That could be rewritten as:
temp = both.getOrDefault(key, 0);
if (j > temp)
both.put(key, j)
Which could be rewritten as:
if (j > both.getOrDefault(key, 0))
both.put(key, j);
I also see code like this in a few places:
while (j < word.length() && word.charAt(0) == word.charAt(j)) {
j++;
}
int key = word.charAt(0);
Why are you writing word.charAt(0)
more than one time? Define the key
above the loop, and make things shorter, clearer, and simpler:
int key = word.charAt(0);
while (j < word.length() && key == word.charAt(j)) {
j++;
}
In your bottom section, you can remove a lot of that code using the map-with-default-value approach. The best answer is the one that has the largest total of prefix + both + suffix, where the default for any of them is zero. Also, res
is a bad name. Try longest
.
for (Integer key : prefix.keySet()) {
longest_for_key = prefix.getOrDefault(key, 0) + both.getOrDefault(key, 0) + suffix.getOrDefault(key, 0);
if (longest_for_key > longest)
longest = longest_for_key;
}
You'll still have to do all three, since there might be a unique key in one of the maps with a dominant string. But as least the code is simpler.
$endgroup$
add a comment |
$begingroup$
Your code repeats in many places. Instead of using if (map.containsKey)
, you should make good use of Map.getOrDefault
:
map.put(key, j + map.getOrDefault(key, 0));
That way you can convert many five-liners into one-liners.
Instead of the <
operator just use Math.max
, which leads to shorter code as well.
I don't understand the formatting of the code, especially why the methods are indented by 11 spaces. If there's no hidden meaning to it, let your IDE or editor format the code automatically.
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
});
});
}, "mathjax-editing");
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: "196"
};
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: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
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
});
}
});
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%2fcodereview.stackexchange.com%2fquestions%2f213689%2fconcatenate-words-in-such-a-way-as-to-obtain-the-longest-possible-sub-string-of%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
I think I see a few bugs:
In the initial processing loop, your handling for the
both
case appears wrong. If you have words 'aa' and 'aaa', you would not replace the 2 with a 3, but rather you would add the 2+3 getting 5, since you can concatenate the words as 'aaaaa'.
In the prefix/suffix handling, there is the possibility that the same word would be the largest prefix and suffix, which is an impossibility. Consider a test case like this:
String arr = { "xxbxxx", "xbx", "x" }; // note: xx(2)bxxx(3)
res = solution(arr);
What should
res
be? I believe you will compute theprefix['x']
as being 3, and thesuffix['x']
as being 2, yielding an answer of 6. But the correct answer is 5, since you cannot use "xxbxxx" twice.
(Note: This is a significant problem, since if true it will require you to significantly change how you are implementing your solution.)
In the final phase, computing results, your
prefix
andsuffix
loops ignore the possibility of a single winner. That is,prefix
requires asuffix
to win, andsuffix
requires aprefix
to win. It does not allow for the possibility that a word like "xzzzzzzzzzz" could have a long enough (prefix|suffix) to just dominate the result.The same is true for
both
: there is no acknowledgement of the possibility of a prefix+both+suffix.
And now here's some non-bug stuff:
You spend a lot of time checking if a map contains a given key. If you go through and count lines of code, it is probably the most expensive thing you do. (Not to mention that many of your bugs are around this area.) I think it would benefit you to set up your maps so that the keys were always present with a default value of zero. There are some proposed options in this SO question.
For a specific example, consider this:
if (both.containsKey(key)) {
Integer temp = both.get(key);
if (j > temp) {
both.put(key, j);
}
} else {
both.put(key, j);
}
That could be rewritten as:
temp = both.getOrDefault(key, 0);
if (j > temp)
both.put(key, j)
Which could be rewritten as:
if (j > both.getOrDefault(key, 0))
both.put(key, j);
I also see code like this in a few places:
while (j < word.length() && word.charAt(0) == word.charAt(j)) {
j++;
}
int key = word.charAt(0);
Why are you writing word.charAt(0)
more than one time? Define the key
above the loop, and make things shorter, clearer, and simpler:
int key = word.charAt(0);
while (j < word.length() && key == word.charAt(j)) {
j++;
}
In your bottom section, you can remove a lot of that code using the map-with-default-value approach. The best answer is the one that has the largest total of prefix + both + suffix, where the default for any of them is zero. Also, res
is a bad name. Try longest
.
for (Integer key : prefix.keySet()) {
longest_for_key = prefix.getOrDefault(key, 0) + both.getOrDefault(key, 0) + suffix.getOrDefault(key, 0);
if (longest_for_key > longest)
longest = longest_for_key;
}
You'll still have to do all three, since there might be a unique key in one of the maps with a dominant string. But as least the code is simpler.
$endgroup$
add a comment |
$begingroup$
I think I see a few bugs:
In the initial processing loop, your handling for the
both
case appears wrong. If you have words 'aa' and 'aaa', you would not replace the 2 with a 3, but rather you would add the 2+3 getting 5, since you can concatenate the words as 'aaaaa'.
In the prefix/suffix handling, there is the possibility that the same word would be the largest prefix and suffix, which is an impossibility. Consider a test case like this:
String arr = { "xxbxxx", "xbx", "x" }; // note: xx(2)bxxx(3)
res = solution(arr);
What should
res
be? I believe you will compute theprefix['x']
as being 3, and thesuffix['x']
as being 2, yielding an answer of 6. But the correct answer is 5, since you cannot use "xxbxxx" twice.
(Note: This is a significant problem, since if true it will require you to significantly change how you are implementing your solution.)
In the final phase, computing results, your
prefix
andsuffix
loops ignore the possibility of a single winner. That is,prefix
requires asuffix
to win, andsuffix
requires aprefix
to win. It does not allow for the possibility that a word like "xzzzzzzzzzz" could have a long enough (prefix|suffix) to just dominate the result.The same is true for
both
: there is no acknowledgement of the possibility of a prefix+both+suffix.
And now here's some non-bug stuff:
You spend a lot of time checking if a map contains a given key. If you go through and count lines of code, it is probably the most expensive thing you do. (Not to mention that many of your bugs are around this area.) I think it would benefit you to set up your maps so that the keys were always present with a default value of zero. There are some proposed options in this SO question.
For a specific example, consider this:
if (both.containsKey(key)) {
Integer temp = both.get(key);
if (j > temp) {
both.put(key, j);
}
} else {
both.put(key, j);
}
That could be rewritten as:
temp = both.getOrDefault(key, 0);
if (j > temp)
both.put(key, j)
Which could be rewritten as:
if (j > both.getOrDefault(key, 0))
both.put(key, j);
I also see code like this in a few places:
while (j < word.length() && word.charAt(0) == word.charAt(j)) {
j++;
}
int key = word.charAt(0);
Why are you writing word.charAt(0)
more than one time? Define the key
above the loop, and make things shorter, clearer, and simpler:
int key = word.charAt(0);
while (j < word.length() && key == word.charAt(j)) {
j++;
}
In your bottom section, you can remove a lot of that code using the map-with-default-value approach. The best answer is the one that has the largest total of prefix + both + suffix, where the default for any of them is zero. Also, res
is a bad name. Try longest
.
for (Integer key : prefix.keySet()) {
longest_for_key = prefix.getOrDefault(key, 0) + both.getOrDefault(key, 0) + suffix.getOrDefault(key, 0);
if (longest_for_key > longest)
longest = longest_for_key;
}
You'll still have to do all three, since there might be a unique key in one of the maps with a dominant string. But as least the code is simpler.
$endgroup$
add a comment |
$begingroup$
I think I see a few bugs:
In the initial processing loop, your handling for the
both
case appears wrong. If you have words 'aa' and 'aaa', you would not replace the 2 with a 3, but rather you would add the 2+3 getting 5, since you can concatenate the words as 'aaaaa'.
In the prefix/suffix handling, there is the possibility that the same word would be the largest prefix and suffix, which is an impossibility. Consider a test case like this:
String arr = { "xxbxxx", "xbx", "x" }; // note: xx(2)bxxx(3)
res = solution(arr);
What should
res
be? I believe you will compute theprefix['x']
as being 3, and thesuffix['x']
as being 2, yielding an answer of 6. But the correct answer is 5, since you cannot use "xxbxxx" twice.
(Note: This is a significant problem, since if true it will require you to significantly change how you are implementing your solution.)
In the final phase, computing results, your
prefix
andsuffix
loops ignore the possibility of a single winner. That is,prefix
requires asuffix
to win, andsuffix
requires aprefix
to win. It does not allow for the possibility that a word like "xzzzzzzzzzz" could have a long enough (prefix|suffix) to just dominate the result.The same is true for
both
: there is no acknowledgement of the possibility of a prefix+both+suffix.
And now here's some non-bug stuff:
You spend a lot of time checking if a map contains a given key. If you go through and count lines of code, it is probably the most expensive thing you do. (Not to mention that many of your bugs are around this area.) I think it would benefit you to set up your maps so that the keys were always present with a default value of zero. There are some proposed options in this SO question.
For a specific example, consider this:
if (both.containsKey(key)) {
Integer temp = both.get(key);
if (j > temp) {
both.put(key, j);
}
} else {
both.put(key, j);
}
That could be rewritten as:
temp = both.getOrDefault(key, 0);
if (j > temp)
both.put(key, j)
Which could be rewritten as:
if (j > both.getOrDefault(key, 0))
both.put(key, j);
I also see code like this in a few places:
while (j < word.length() && word.charAt(0) == word.charAt(j)) {
j++;
}
int key = word.charAt(0);
Why are you writing word.charAt(0)
more than one time? Define the key
above the loop, and make things shorter, clearer, and simpler:
int key = word.charAt(0);
while (j < word.length() && key == word.charAt(j)) {
j++;
}
In your bottom section, you can remove a lot of that code using the map-with-default-value approach. The best answer is the one that has the largest total of prefix + both + suffix, where the default for any of them is zero. Also, res
is a bad name. Try longest
.
for (Integer key : prefix.keySet()) {
longest_for_key = prefix.getOrDefault(key, 0) + both.getOrDefault(key, 0) + suffix.getOrDefault(key, 0);
if (longest_for_key > longest)
longest = longest_for_key;
}
You'll still have to do all three, since there might be a unique key in one of the maps with a dominant string. But as least the code is simpler.
$endgroup$
I think I see a few bugs:
In the initial processing loop, your handling for the
both
case appears wrong. If you have words 'aa' and 'aaa', you would not replace the 2 with a 3, but rather you would add the 2+3 getting 5, since you can concatenate the words as 'aaaaa'.
In the prefix/suffix handling, there is the possibility that the same word would be the largest prefix and suffix, which is an impossibility. Consider a test case like this:
String arr = { "xxbxxx", "xbx", "x" }; // note: xx(2)bxxx(3)
res = solution(arr);
What should
res
be? I believe you will compute theprefix['x']
as being 3, and thesuffix['x']
as being 2, yielding an answer of 6. But the correct answer is 5, since you cannot use "xxbxxx" twice.
(Note: This is a significant problem, since if true it will require you to significantly change how you are implementing your solution.)
In the final phase, computing results, your
prefix
andsuffix
loops ignore the possibility of a single winner. That is,prefix
requires asuffix
to win, andsuffix
requires aprefix
to win. It does not allow for the possibility that a word like "xzzzzzzzzzz" could have a long enough (prefix|suffix) to just dominate the result.The same is true for
both
: there is no acknowledgement of the possibility of a prefix+both+suffix.
And now here's some non-bug stuff:
You spend a lot of time checking if a map contains a given key. If you go through and count lines of code, it is probably the most expensive thing you do. (Not to mention that many of your bugs are around this area.) I think it would benefit you to set up your maps so that the keys were always present with a default value of zero. There are some proposed options in this SO question.
For a specific example, consider this:
if (both.containsKey(key)) {
Integer temp = both.get(key);
if (j > temp) {
both.put(key, j);
}
} else {
both.put(key, j);
}
That could be rewritten as:
temp = both.getOrDefault(key, 0);
if (j > temp)
both.put(key, j)
Which could be rewritten as:
if (j > both.getOrDefault(key, 0))
both.put(key, j);
I also see code like this in a few places:
while (j < word.length() && word.charAt(0) == word.charAt(j)) {
j++;
}
int key = word.charAt(0);
Why are you writing word.charAt(0)
more than one time? Define the key
above the loop, and make things shorter, clearer, and simpler:
int key = word.charAt(0);
while (j < word.length() && key == word.charAt(j)) {
j++;
}
In your bottom section, you can remove a lot of that code using the map-with-default-value approach. The best answer is the one that has the largest total of prefix + both + suffix, where the default for any of them is zero. Also, res
is a bad name. Try longest
.
for (Integer key : prefix.keySet()) {
longest_for_key = prefix.getOrDefault(key, 0) + both.getOrDefault(key, 0) + suffix.getOrDefault(key, 0);
if (longest_for_key > longest)
longest = longest_for_key;
}
You'll still have to do all three, since there might be a unique key in one of the maps with a dominant string. But as least the code is simpler.
answered 37 mins ago
Austin HastingsAustin Hastings
6,5541232
6,5541232
add a comment |
add a comment |
$begingroup$
Your code repeats in many places. Instead of using if (map.containsKey)
, you should make good use of Map.getOrDefault
:
map.put(key, j + map.getOrDefault(key, 0));
That way you can convert many five-liners into one-liners.
Instead of the <
operator just use Math.max
, which leads to shorter code as well.
I don't understand the formatting of the code, especially why the methods are indented by 11 spaces. If there's no hidden meaning to it, let your IDE or editor format the code automatically.
$endgroup$
add a comment |
$begingroup$
Your code repeats in many places. Instead of using if (map.containsKey)
, you should make good use of Map.getOrDefault
:
map.put(key, j + map.getOrDefault(key, 0));
That way you can convert many five-liners into one-liners.
Instead of the <
operator just use Math.max
, which leads to shorter code as well.
I don't understand the formatting of the code, especially why the methods are indented by 11 spaces. If there's no hidden meaning to it, let your IDE or editor format the code automatically.
$endgroup$
add a comment |
$begingroup$
Your code repeats in many places. Instead of using if (map.containsKey)
, you should make good use of Map.getOrDefault
:
map.put(key, j + map.getOrDefault(key, 0));
That way you can convert many five-liners into one-liners.
Instead of the <
operator just use Math.max
, which leads to shorter code as well.
I don't understand the formatting of the code, especially why the methods are indented by 11 spaces. If there's no hidden meaning to it, let your IDE or editor format the code automatically.
$endgroup$
Your code repeats in many places. Instead of using if (map.containsKey)
, you should make good use of Map.getOrDefault
:
map.put(key, j + map.getOrDefault(key, 0));
That way you can convert many five-liners into one-liners.
Instead of the <
operator just use Math.max
, which leads to shorter code as well.
I don't understand the formatting of the code, especially why the methods are indented by 11 spaces. If there's no hidden meaning to it, let your IDE or editor format the code automatically.
answered 17 mins ago
Roland IlligRoland Illig
11.1k11844
11.1k11844
add a comment |
add a comment |
Thanks for contributing an answer to Code Review Stack Exchange!
- 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.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
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%2fcodereview.stackexchange.com%2fquestions%2f213689%2fconcatenate-words-in-such-a-way-as-to-obtain-the-longest-possible-sub-string-of%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
$begingroup$
In
solution
, your handling for theboth
case appears wrong. If you have words 'aa' and 'aaa', you would not replace the 2 with a 3, but rather you would add the 2+3 getting 5, since you can concatenate the words as 'aaaaa', right?$endgroup$
– Austin Hastings
1 hour ago
$begingroup$
@AustinHastings you are right. I have missed it.
$endgroup$
– Maclean Pinto
55 mins ago
$begingroup$
@AustinHastings updated line 43 to both.put(key, j + temp); This should solve it.
$endgroup$
– Maclean Pinto
45 mins ago