Concatenate words in such a way as to obtain the longest possible sub-string of the same letter












3












$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:


    1. 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.

    2. 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.




 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?










share|improve this question











$endgroup$












  • $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 updated line 43 to both.put(key, j + temp); This should solve it.
    $endgroup$
    – Maclean Pinto
    45 mins ago
















3












$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:


    1. 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.

    2. 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.




 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?










share|improve this question











$endgroup$












  • $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 updated line 43 to both.put(key, j + temp); This should solve it.
    $endgroup$
    – Maclean Pinto
    45 mins ago














3












3








3





$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:


    1. 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.

    2. 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.




 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?










share|improve this question











$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:


    1. 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.

    2. 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.




 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






share|improve this question















share|improve this question













share|improve this question




share|improve this question








edited 44 mins ago







Maclean Pinto

















asked 1 hour ago









Maclean PintoMaclean Pinto

1395




1395












  • $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 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$
    @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










2 Answers
2






active

oldest

votes


















2












$begingroup$

I think I see a few bugs:




  1. 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'.



  2. 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 the prefix['x'] as being 3, and the suffix['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.)



  3. In the final phase, computing results, your prefix and suffix loops ignore the possibility of a single winner. That is, prefix requires a suffix to win, and suffix requires a prefix 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.


  4. 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.






share|improve this answer









$endgroup$





















    1












    $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.






    share|improve this answer









    $endgroup$













      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
      });


      }
      });














      draft saved

      draft discarded


















      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









      2












      $begingroup$

      I think I see a few bugs:




      1. 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'.



      2. 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 the prefix['x'] as being 3, and the suffix['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.)



      3. In the final phase, computing results, your prefix and suffix loops ignore the possibility of a single winner. That is, prefix requires a suffix to win, and suffix requires a prefix 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.


      4. 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.






      share|improve this answer









      $endgroup$


















        2












        $begingroup$

        I think I see a few bugs:




        1. 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'.



        2. 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 the prefix['x'] as being 3, and the suffix['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.)



        3. In the final phase, computing results, your prefix and suffix loops ignore the possibility of a single winner. That is, prefix requires a suffix to win, and suffix requires a prefix 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.


        4. 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.






        share|improve this answer









        $endgroup$
















          2












          2








          2





          $begingroup$

          I think I see a few bugs:




          1. 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'.



          2. 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 the prefix['x'] as being 3, and the suffix['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.)



          3. In the final phase, computing results, your prefix and suffix loops ignore the possibility of a single winner. That is, prefix requires a suffix to win, and suffix requires a prefix 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.


          4. 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.






          share|improve this answer









          $endgroup$



          I think I see a few bugs:




          1. 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'.



          2. 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 the prefix['x'] as being 3, and the suffix['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.)



          3. In the final phase, computing results, your prefix and suffix loops ignore the possibility of a single winner. That is, prefix requires a suffix to win, and suffix requires a prefix 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.


          4. 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.







          share|improve this answer












          share|improve this answer



          share|improve this answer










          answered 37 mins ago









          Austin HastingsAustin Hastings

          6,5541232




          6,5541232

























              1












              $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.






              share|improve this answer









              $endgroup$


















                1












                $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.






                share|improve this answer









                $endgroup$
















                  1












                  1








                  1





                  $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.






                  share|improve this answer









                  $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.







                  share|improve this answer












                  share|improve this answer



                  share|improve this answer










                  answered 17 mins ago









                  Roland IlligRoland Illig

                  11.1k11844




                  11.1k11844






























                      draft saved

                      draft discarded




















































                      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.




                      draft saved


                      draft discarded














                      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





















































                      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







                      Popular posts from this blog

                      Bundesstraße 106

                      Verónica Boquete

                      Ida-Boy-Ed-Garten