Build a String Algorithm

Question

I am trying to solve and understand the Build a String problem,

this piece of code pass 6 test cases and then failed, I got one failed test case but I am not able to understand why it is failed, could anyone explain why?

Test case

Input

a = 7890 
b = 7891
s = acbcrsjcrscrsjcrcbcrsjcrscrsjccbcrsjcrscrsjcrcbcrsjrscrsjcrcbcrsjcrscrsjccbcrsjcrscrsjcrcbcsbcbcrsjh

Expected : 126246

Actually : 126247

static int buildString(int a, int b, String s) {
        int result = 0;
        String initial = "";
        while (!s.equals("")) {
            final String substring = s.substring(0, 1);
            if (!initial.contains(substring)) {
                initial += substring;
                result += a;
                s = s.substring(1);
            } else {
                String last = "";
                for (int i = 1; i <= s.length(); i++) {
                    final String substring1 = s.substring(0, i);
                    if (initial.contains(substring1)) {
                        last = substring1;
                    } else {
                        break;
                    }
                }
                if (last.equals(substring) || b > (last.length() * a)) {
                    initial += substring;
                    result += a;
                    s = s.substring(1);
                } else {
                    initial += last;
                    result += b;
                    s = s.substring(last.length());
                }

            }
        }
        return result;
    }

Answer 1

As you are using greedy algorithm, which try to append longest substring (operation b) whenever possible, and add one character in the end (operation a) if operation b is not possible, the steps are as follow.

Step	Operation	Result
1	a	a
2	a	ac
3	a	acb
4	a	acbc
5	a	acbcr
6	a	acbcrs
7	a	acbcrsj
8	b	acbcrsjcrs
9	b	acbcrsjcrscrsjcr
10	b	acbcrsjcrscrsjcrcbcrsjcrscrsjc
11	b	acbcrsjcrscrsjcrcbcrsjcrscrsjccbcrsjcrscrsjcrcbcrsj
12	b	acbcrsjcrscrsjcrcbcrsjcrscrsjccbcrsjcrscrsjcrcbcrsjrscrsjcrcbcrsjcrscrsjccbcrsjcrscrsjcrcbc
13	a	acbcrsjcrscrsjcrcbcrsjcrscrsjccbcrsjcrscrsjcrcbcrsjrscrsjcrcbcrsjcrscrsjccbcrsjcrscrsjcrcbcs
14	b	acbcrsjcrscrsjcrcbcrsjcrscrsjccbcrsjcrscrsjcrcbcrsjrscrsjcrcbcrsjcrscrsjccbcrsjcrscrsjcrcbcsbc
15	b	acbcrsjcrscrsjcrcbcrsjcrscrsjccbcrsjcrscrsjcrcbcrsjrscrsjcrcbcrsjcrscrsjccbcrsjcrscrsjcrcbcsbcbcrsj
16	a	acbcrsjcrscrsjcrcbcrsjcrscrsjccbcrsjcrscrsjcrcbcrsjrscrsjcrcbcrsjcrscrsjccbcrsjcrscrsjcrcbcsbcbcrsjh

In step 14, "bc" is added to the end, which can be replaced by a "a" operation which just add "b" to the end, and then in step 15, we can add "cbcrsj" in the end. Hence 1 "b" operation is replaced by 1 "a" operation and the result is 126246.

To fix the problem, you should use dynamic programming in such case.

Answer 2

Here is a simple solution via iteration, in Java.

---

Code

BuildString.java

public class BuildString {
    /**
     * Build a string.
     *
     * @param s the string to build,
     * @param a point to append a char,
     * @param b point to append a substring of existing part, b >= a,
     * @return total point used,
     */
    public static int build(String s, int a, int b) {
        return build(s, a, b, new StringBuilder());
    }

    /**
     * Build step by step, via iteration.
     *
     * @param s
     * @param a
     * @param b
     * @param sb the built part,
     * @return
     */
    private static int build(String s, int a, int b, StringBuilder sb) {
        int point = 0;

        while (sb.length() < s.length()) {
            String subStr = findMaxSubStr(sb, s);
            if (subStr != null) {
                sb.append(subStr);
                point += b;
            } else {
                sb.append(s.charAt(sb.length()));
                point += a;
            }
        }

        return point;
    }

    /**
     * Find next max substring with length >= 2.
     *
     * @param sb the existing part,
     * @param s  the original string.
     * @return next max substring with length >= 2, or null if not exists,
     */
    private static String findMaxSubStr(StringBuilder sb, String s) {
        // TODO ... improve with cache ?
        int sLen = s.length();
        int sbLen = sb.length();

        for (int i = sLen - sbLen; i > 1; i--) {
            String target = s.substring(sbLen, sbLen + i);
            if (sb.indexOf(target) >= 0) return target; // found,
        }

        return null; // not found,
    }
}

BuildStringTest.java
(Test case - via TestNG)

import org.testng.Assert;
import org.testng.annotations.Test;

import static org.testng.Assert.*;

public class BuildStringTest {
    @Test
    public void testBuild() {
        testOnce("aabaacaba", 4, 5, 26);
        testOnce("bacbacacb", 8, 9, 42);
    }

    @Test
    public void testCorner() {
        testOnce("", 4, 5, 0); // empty string,
        testOnce("a", 4, 5, 4); // single char,
    }

    private void testOnce(String s, int a, int b, int expectedPoint) {
        int point = BuildString.build(s, a, b);
        System.out.printf("s = '%s', a = %d, b = %d, expected point: %d,\t actual point: %d\n", s, a, b, expectedPoint, point);
        Assert.assertEquals(point, expectedPoint);
    }
}

---

Complexity

• Time: O(n^2)
• Space: O(n)

---

TODO

• I guess could use some kind of cache to speed up searching of next max substring, to improve the time complexity.