11
\$\begingroup\$

Given a string and a non-negative int n, we'll say that the front of the string is the first 3 chars, or whatever is there if the string is less than length 3. Return n copies of the front:

frontTimes("Chocolate", 2) → "ChoCho"
frontTimes("Chocolate", 3) → "ChoChoCho"
frontTimes("Abc", 3) → "AbcAbcAbc"
frontTimes("X", 3) → "XXX"

I've solved above problem using following code but I'm using a new StringBuilder to store intermediate string result. Does it really needed can I optimize and remove the for loop in the else?

public String frontTimes(String str, int n) {

        StringBuilder sb = new StringBuilder(str);
        StringBuilder newsb = new StringBuilder();

        if(sb.length() >= 3)
        {
            for(int i = 0; i < n; i++)
            {
                newsb.append(sb.substring(0,3));
            }

            return newsb.toString(); 
        }
        else
        {
            for(int i = 0; i < n; i++)
            {
                newsb.append(sb.toString());
            }

            return newsb.toString();

        }

    }
\$\endgroup\$
13
\$\begingroup\$

I'd just like to make a slight change to the code. When you are instantiating a StringBuilder, you have the opportunity to specify the capacity of it. Using this constructor, we can avoid having it resized more than necessary.

public String frontTimes(String str, int n) {
    StringBuilder stringBuilder = new StringBuilder(3 * n);
    if (str.length() > 3) {
        str = str.substring(0, 3);
    }
    for (int i = 0; i < n; i++) {
        stringBuilder.append(str);
    }
    return stringBuilder.toString();
}

Note how many times that 3 is declared? Would be better to extract that to a constant, or even better, a parameter. And with a few other changes to the above (as suggested by @rolfl in chat):

public String frontTimes(final String str, final int frontLength, final int times) {
    String copyString = str.length() > frontLength ? str.substring(0, frontLength) : str;
    StringBuilder stringBuilder = new StringBuilder(copyString.length() * times);
    for (int i = 0; i < times; i++) {
        stringBuilder.append(copyString);
    }
    return stringBuilder.toString();
}
\$\endgroup\$
  • \$\begingroup\$ instanciate the stringBuilder after substring so you can use str.length() * n as capacity. \$\endgroup\$ – Guillaume Jan 28 '15 at 11:04
  • \$\begingroup\$ @Guillaume fixed in the second version now, thanks. \$\endgroup\$ – Simon Forsberg Jan 28 '15 at 11:09
10
\$\begingroup\$

I am a fan of using primitives. In this case, the performance benefit would be minimal, but the number of copies would actually be less.....

In reality, I would probably use the StringBuilder approach similar to what other answers have given (+1 to them all), but you should be aware that the following code is likely faster, has fewer iterations through the loop, and will scale better..... if you ever need to make millions of copies... ;-) (now here with a cheesy test case in ideone too)

/**
 * Using the input source string, duplicate its prefix the specified count
 * times.
 * @param source       The source string containing the prefix
 * @param prefixLength The length of the prefix to use (or the whole string
 *                     if the prefix is larger than the String)
 * @param count        the number of times to repeat the prefix.
 * @return the resulting duplicated string, or an empty string if the source
 *         is invalid or the count or prefix length is zero
 */
public static String duplicatePrefix(final String source, final int prefixLength, final int count) {
    if (source == null || source.length() == 0 || prefixLength <= 0 || count <= 0) {
        return "";
    }

    final int actual = Math.min(source.length(), prefixLength);
    final int size = actual * count;
    final char[] results = new char[size];
    // copy the first prefix to the output
    source.getChars(0, actual, results, 0);
    // duplicate the previously populated chars as often as needed.
    int currentpos = actual;
    while (currentpos < size) {
        // copy as much as you can, limited by the available space to copy to.
        System.arraycopy(results, 0, results, currentpos, Math.min(currentpos, size - currentpos));
        // double the current position
        currentpos <<= 1;
    }
    return new String(results);
}

Note that the loop in the above code will iterate only \$\log(count)\$ times where, which can be a significant saving in the event that count is large, though the ArrayCopy is still an \$O(n)\$ operation, so it is a toss up as to whether it will improve the speed at all... it will need some benchmarking.

\$\endgroup\$
  • 1
    \$\begingroup\$ Hmm..It's minor, but replacing the first copy with source.getChars(0, actual, results, 0) seems best in that case to avoid unnecessary intermediate allocations. \$\endgroup\$ – Tim Stone Jan 27 '15 at 23:10
  • \$\begingroup\$ You're right, that will help, why didn't I thin of that, @TimStone ? \$\endgroup\$ – rolfl Jan 27 '15 at 23:11
  • \$\begingroup\$ I haven't had nearly enough caffeine today, but I think that second Math.min() might be off as well, isn't it meant to be Math.min(currentpos, size - currentpos)? And I promise I didn't randomly show up to pick on you, you can blame the Hot Questions list ;) \$\endgroup\$ – Tim Stone Jan 27 '15 at 23:34
  • \$\begingroup\$ @TimStone - Nahhh, I like the Hot list, but I am pretty sure the second min is fine... it works for me (I was running the code in a simple test system I have not posted...). \$\endgroup\$ – rolfl Jan 27 '15 at 23:36
  • \$\begingroup\$ I might be logic-ing wrong, it seems like it will always take actual (since size and currentpos are multiples of actual), and that's copying less than what is intended (everything written thusfar, i.e. currentpos, or the remaining space, size - currentpos). \$\endgroup\$ – Tim Stone Jan 27 '15 at 23:38
6
\$\begingroup\$

I think the StringBuilder sb isn't necessary.

public String frontTimes(String str, int n)
{
    StringBuilder newsb = new StringBuilder();

    if (str.Length >= 3) str = str.substring(0, 3);

    for (int i = 0; i < n; i++)
    {
        newsb.append(str);
    }

    return newsb.ToString();
}
\$\endgroup\$
  • 6
    \$\begingroup\$ I agree with your comment about sb but disagree with reusing str variable name and writing an if statement on a single line. Btw, your code will not compile with javac... \$\endgroup\$ – mkalkov Jan 27 '15 at 16:21
  • \$\begingroup\$ I don't like the reuse of method args, str and n should be final \$\endgroup\$ – user131519 Jun 2 '17 at 8:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.