Build String Hackerrank

Question

Online challenge on Hacker Rank.

Please follow the description from the above link.

import java.util.Set;
import java.util.HashSet;
import java.util.List;
import java.util.ArrayList;

class Main {
  private static List<String> substrings(String s) {
    int length = s.length();
    List<String> list = new ArrayList<>();

    for (int i = 0; i < length; i++) {
      for (int j = i + 1; j <= length; j++) {
        list.add(s.substring(i, j));
      }
    }
    return list;
  }

  private static int solve(String text, int A, int C) {
    int length = text.length();
    StringBuilder sb = new StringBuilder(length);
    Set<String> set  = new HashSet<>();

    int cost = 0;
    int len  = 0;
    for (int i = 0; i < length; i++) {
      len = sb.length();
      if (len == 0) {
        sb.append(text.charAt(0));
        set.add(sb.toString());
        cost += A;
        continue;
      }

      while (len > 0) {
        int sum = i + len;
        int end = (sum > length) ? length : sum;
        String lookAhead = text.substring(i, end);
        if (set.contains(lookAhead)) {
          if (lookAhead.length() == 1 && A <= C) {
            cost += A;
          } else {
            cost += C;  
          }

          i += len - 1;
          sb.append(lookAhead);
          for (String sub : substrings(sb.toString())) {
            set.add(sub);
          } // end for
          break;
        } // end if
        else {
          if (lookAhead.length() == 1) {
            cost += A;
            sb.append(lookAhead);
            for (String sub : substrings(sb.toString())) {
              set.add(sub);
            } // end for
            break;
          }
          len--;
        } // end else
      } // end while
    } // end for
    //return sb.toString();
    return cost;
  }

  public static void main(String[] args) {
    System.out.println(solve("a", 4, 5));   // 4 A 
    System.out.println(solve("ab", 4, 5));  // 8 A + A
    System.out.println(solve("aba", 4, 3)); // 11 A + A + C
    System.out.println(solve("aabaacaba", 4, 5)); // 26 A + A + A + C + A + C
    System.out.println(solve("bacbacacb", 8, 9)); // 42 A + A + A + C + C
  }
}

Note:

I have to confess this time that I really didn't know what I was doing, I spent more than couple of hours on this problem and still its faling on some test cases and times out (which I knew since its kind of brute force).

The only positive things that I can conclude from my not so worthy effort is although I came up with the basic idea pretty fast but in process of writing code I was really struggling to follow the flow and had to dance with the logic for more than an hour basically I had a hard time converting my idea to code.

Any suggestion would be really helpful as I have some major interview in couple of days so, some tips would defintely help.

Second and most important thing is that how to check the correctness of such algorithms since I had to print values several times and it became very painful.

Apart from that I would like to know an effcient algorithm.

Answer 1

  private static List<String> substrings(String s) {

Concerning speed, this is the first bug. There are too many substrings O(n**2) and generating all of them is wasting O(n**3) time (as the copying has linear complexity). You're using it in a loop, so it may be O(n**4), really slow.

It'd be slightly better to generate a Set rather than a List. Given the input aabaacaba, there are quite some substrings repeated. I see, you're using a Set later. You could avoid any intermediate collection when you implemented

private static void addSubstringsTo(Collection<String> result, String s)`

instead.

But this is a minor optimization. A much bigger one would be to observe, that all substrings are already there, except for those ending on the current position.

But even this is by far not the fastest way.

---

 if (len == 0) {

This seems to be superfluous. Sure, you can only append, but the reason is that there are no usable substrings. So you can save this test and proceed in the usual way.

} // end for

Please don't. Keep your method short enough so that such garbage is unnecessary. While IIRC the style guide requires indentantion of 2 spaces, I use 4, so that the code structure is easier to see.

---

int length = text.length();
...
int len  = 0;

That's crazy. len is a pretty common abbreviation for length, many dislike it, I find it acceptable. But using both in the same method is perverted.

---

int end = (sum > length) ? length : sum;

You surely mean

int end = Math.min(sum, length);

It's the same, but it doesn't make me think.

---

} // end if
    else {
      if (lookAhead.length() == 1) {

You're repeating yourself in the code below this. Something like

if (lookAhead.length() == 1 || set.contains(lookAhead)) {
    ... append, update the set, break
}

should work.

---

You could get some speed by not generating the strings. While the HashSet lookup is very fast, you're putting therein much more strings than you can ever use... so you're wasting time. Something like

 text.substring(0, i).lastIndexOf(lookAhead)

should be faster. But still not perfect.

---

Concerning the cost optimization, you're making at least two mistakes.

It's possible that appending a substring costs more than appending a character twice, so you probably should look at A * lookAhead.length() compared to C (which is called B in the linked challenge).

You're using a greedy strategy. Appending some string may be advantageous at a moment, but it may prevent appending a much longer string later. I guess, you should always explore every possibility, except when one is clearly worse than some other. By "clearly worse" I actually mean "the same string at higher cost" as a shorter string may be better sometimes.

---

Concerning speed, I guess, not generating any strings is the way to go. As the text is given, all you need is to remember the substring indexes. Calling substring is wasting time, create a trivial immutable class containing start and end instead.

An exactly optimizing algorithm would probably keep track of the cheapest way of creating text.substring(0, i) for every value of i. In each step, it'd try to build a longer substring and store or update its cost. It's not trivial and I haven't solved it yet, so I can't give more details. But look at dynamic programming, which is the general way of solving such problems.

Slow code

Note that one big problem with your algorithm is that it's too long. You wrote "I really didn't know what I was doing" and I trust you on it. This happens to everyone, when the code gets too long and/or disorganized. Refactoring (e.g., extracting methods or classes) is the way to go (thought sometimes rewriting the good parts from scratch is better).

Without much thinking I wrote this O(3) code. It solves 10 test cases out of 21, when it fails, it's due to timeout.

private static int solve(int a, int b, String text) {
    // Cost as a function of length.
    final int costs[] = new int[text.length() + 1];
    Arrays.fill(costs, Integer.MAX_VALUE);
    costs[0] = 0; // Empty string is free.

    // Minimum length to be copied (as copying less is not worth it).
    final int minLen = Math.min(1, b / a);
    for (int i=1; i<costs.length; ++i) {
        costs[i] = Math.min(costs[i], costs[i-1] + a);
        final String start = text.substring(0, i);

        // We copy no more than we have and no more than we need.
        for (int len=minLen; len<=i && i+len<costs.length; ++len) {
            boolean found = start.contains(text.substring(i, i+len));
            if (!found) break;
            costs[i+len] = Math.min(costs[i+len], costs[i] + b);
        }
    }
    return costs[text.length()];
}