6
\$\begingroup\$

I came across this problem in a career cup. Below I have the questions and the Java solution. I was wondering if anyone could scrutinize my code and tell me if there are any improvements, or better coding practices that I should know, as I am working on being able to produce proficient code.

Problem statement:

Write a program to accept a nonempty string of alphanumeric characters. Define a run as a consecutive sequence of a single character. For example, aaaa is a run of length \$4\$. The program will print the longest run in the given string. If there is no single longest run, then you may print any of those runs whose length is at least as long as all other runs in the string.

Example input: a 

Example output: a 

Example input: aab 

Example output: aa 

Example input: abbbbbcc 

Example output: bbbbb 

Example input: aabbccdd 

Example output: aa

Solution:

public class StringRunCount {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        System.out.println(maxRun("aaabbbbbbbbcccccc"));
    }

    public static int maxRun(String testString) {
        int len = testString.length();
        String substr = "";
        for (int i = 0; i < len;) {
            char current = testString.charAt(i);
            String tempSubstr = "" + current;
            while ((i + 1) < len && (current == testString.charAt(i + 1))) {
                tempSubstr = tempSubstr + testString.charAt(++i);
            }

            if (tempSubstr.length() >= substr.length()) {
                substr = tempSubstr;

            }
            i += 1;
        }
        System.out.println(substr);
        return substr.length();
    }

}
\$\endgroup\$

migrated from stackoverflow.com Oct 29 '15 at 20:25

This question came from our site for professional and enthusiast programmers.

  • 2
    \$\begingroup\$ Very inefficient. Never do String = String + String in a loop. \$\endgroup\$ – Andreas Oct 29 '15 at 20:28
  • \$\begingroup\$ 1) Construct Strings in loops using StringBuffer or something similar instead of string addition (which is very inefficient). 2) if you know that current == testString.charAt(...), why are you extracting the char again to concatenate to your tempSubStr? Use current instead: tempSubStr += current; \$\endgroup\$ – brimborium Oct 29 '15 at 20:34
10
\$\begingroup\$

You should keep 4 variables:

  • The start index of the longest run
  • The end index (or length) of the longest run
  • The start index of the current run
  • The iterating index

For performance, you'd likely also store the char of the current run in a variable.

When done iterating, return substring of longest run.

\$\endgroup\$
5
\$\begingroup\$

Far too many Strings. Why don't you store just a single character and count its repetitions, then copy the char and the number to some maxchar and maxnum if number > maxnum?

EDIT (code added):

public static int maxRun(String testString) {
    int len = testString.length();
    char maxchar = "!";
    int  maxlen = 0;
    char prevchar = "!";
    int  sublen = 0;

    for (int i = 0; i < len; ++i) {
        char curr = testString.charAt(i);
        if (curr == prevchar) {
            ++sublen;
        }
        else
        {
            if (sublen > maxlen) {
                maxchar = prevchar;
                maxlen = sublen;
            }
            prevchar = curr;
            sublen = 1;
        }
    }

    if (sublen > maxlen) {
        maxchar = prevchar;
        maxlen = sublen;
    }

    for (int i = maxlen; --i >= 0;)
        System.out.print(maxchar);
    System.out.println("");
    return maxlen;
}
\$\endgroup\$
4
\$\begingroup\$

It will be enough and cheaper to track the following variables:

  • The length of the longest run seen so far
  • The length of the current run
  • The previous character
  • The current character

Like this:

public static int longestRun(String testString) {
    int len = testString.length();
    if (len < 2) {
        return len;
    }

    int longest = 0;
    int currentRun = 1;

    char prev = testString.charAt(0);
    for (int i = 1; i < len; ++i) {
        char current = testString.charAt(i);
        if (current == prev) {
            ++currentRun;
        } else {
            if (currentRun > longest) {
                longest = currentRun;
            }
            currentRun = 1;
        }
        prev = current;
    }
    if (currentRun > longest) {
        longest = currentRun;
    }
    return longest;
}

This solution avoids unnecessary string concatenation, that is expensive.

Other notes:

  • Instead of i += 1 at the end of the body of the for loop, it's better to put ++i in the for statement itself
  • Since the purpose of your function is finding the "longest run", naming it longestRun would be more natural than maxRun
\$\endgroup\$
2
\$\begingroup\$

You should honour the "separation of concerns" principle, e.g. not printing something to the console and then returning another value. I think it is better to return the String of the longest sequence (as finding out the length is easy).

I tried my best to use the new Stream API, but here it feels quite awkward (suggestions are welcome):

public static String maxRun(String testString) {
    return testString.chars()
            .mapToObj(i -> (char) i)
            .reduce(new LinkedList<String>(),
                    (l, c) -> {
                        l.add((l.isEmpty() || l.getLast().charAt(0) != c)
                                ? "" + c : l.removeLast() + c);
                        return l;
                    }, (p, q) -> { p.addAll(q); return p; })
            .stream()
            .max(Comparator.comparing(String::length))
            .orElse("");
}
\$\endgroup\$
  • \$\begingroup\$ BTW, I like how more intimidating such a train wreck becomes when you add an orElse at the end... \$\endgroup\$ – Landei Oct 30 '15 at 13:13
  • \$\begingroup\$ Ooh, I didn't know about Comparator#comparing \$\endgroup\$ – lealand Oct 30 '15 at 13:25
2
\$\begingroup\$

Since we're dealing with a String, I suspect that we can use a regular expression to String#split it into chucks for further processing. Specifically, we want a regular expression which will partition every time a character is not like the preceding one. We can do this with lookarounds:

private static final Pattern SPLIT_REGEX = Pattern.compile("(?<=(.))(?!\\1)");

This pattern matches anywhere that:

  • (?<=(.)) given any preceding character we store in group 1 (positive lookbehind),

  • (?!\\1) the following character does not match group 1 (negative lookahead).

So splitting the string aaabbcdd with this regex will produce the array ["aaa", "bb", "c", "dd"].

From there, we can stream and find the max element by string length:

import java.util.Arrays;
import java.util.Comparator;
import java.util.regex.Pattern;

public class StringRunCount {

  private static final Pattern SPLIT_REGEX = Pattern.compile("(?<=(.))(?!\\1)");

  public static String maxRun(final String string) {
    if (null == string) {
      throw new IllegalArgumentException("Argument cannot be null");
    }

    return Arrays.stream(SPLIT_REGEX.split(string))
        .max(Comparator.comparing(String::length))
        .get();
  }

  public static void main(final String[] args) {
    assert "a".equals(maxRun("a"));
    assert "aa".equals(maxRun("aab"));
    assert "bbbbb".equals(maxRun("abbbbbcc"));
    assert "aa".equals(maxRun("aabbccdd"));
  }

}

I learned about Comparator.comparing(String::length) from @Landei's answer, which I'm gracious for because I was expecting to be able to just pass in String::length by itself, originally. I also just call get on the Optional<String> returned by max because we've ruled out the only case the result could be null with our parameter check.

(Note that the last assert isn't necessarily valid, since any other two character substring would suffice.)

\$\endgroup\$

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.