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

It looks like you're using some sort of greedy approach, this problem does not look like it's solvable with greedy approach, you should recode this using dynamic programming, There's lot's of tests that your solution will fail at, i.e. : 100 1 aba — Photon
– Photon, Commented Apr 15, 2020 at 6:11

samabcde · Accepted Answer · 2021-12-28 14:06:10Z

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.

edited Dec 28, 2021 at 14:06

answered Apr 15, 2020 at 6:21

samabcde

8,3043 gold badges30 silver badges47 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

tangolin Over a year ago

at step 13, won't bcrsj be added to the end directly by a greedy algorithm?

samabcde Over a year ago

@tangolin, thx for pointing out, the answer is updated.

Eric · Accepted Answer · 2020-04-20 13:19:10Z

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.

Collectives™ on Stack Overflow

Build a String Algorithm

2 Answers 2

2 Comments

Code

Complexity

TODO

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Code

Complexity

TODO

Comments

Your Answer

Sign up or log in

Post as a guest

Related