Comparing two simple distance calculating algorithms

Question

Is the single method printMaxDistance_a or the two methods printMaxDistance_b AND printMaxDistance_c better or respectively "more readable"? Thanks.

public static void printMaxDistance_a(String s) {
    int first = 0;
    int second = 0;
    int max = 0;
    for (int i = 0; i < s.length(); i++) {
        for (int j = i + 1; j < s.length(); j++) {
            if (s.charAt(i) == s.charAt(j)) {
                if ((j - i) > max) {
                    first = i;
                    second = j;
                    max = j - i;
                }
                break;
            }
        }
    }
    System.out.println(first + " " + second + " " + max);
}

public static void printMaxDistance_b(String s) {
    int first = 0;
    int second = 0;
    int max = 0;
    for (int i = 0; i < s.length(); i++) {
        int cur = printMaxDistance_c(s, s.charAt(i), i + 1);
        if (cur > max) {
            first = i;
            second = i + cur;
            max = cur;
        }
    }
    System.out.println(first + " " + second + " " + max);
}

public static int printMaxDistance_c(String s, char c, int j) {
    for (int i = j; i < s.length(); i++) {
        if (c == s.charAt(i)) {
            return i - (j - 1);
        }
    }
    return 0;
}

@SuppressWarnings("resource")
public static void main(String[] args) {
    String s = new Scanner(System.in).nextLine();
    printMaxDistance_a(s);
    printMaxDistance_b(s);
}

Answer 1

Not more readable with those method names, but in general it is better to split method into more, especially when code is nested like this. I would even go further and split into more than just 2 methods.

But try to name methods so that name clearly says, what method does.

Edit:

Some ideas of what I would change (starting right from _b and _c methods).

• You probably know, that names should be "camelcase", use no underscores and you added underscore just to quickly separate those.

• Method is calculating data and printing them. Those are 2 things at once. What if you wanted to use data instead of printing them? what if you wanted to write them to file or return as part of http response?

  • At first I would at least return String instead of printing it. Then you can do more things than just printing it. That would require renaming method as it doesn't print anymore.
  • That solution is still not ideal, because you are calculating 3 int numbers and instead you are returning String. Instead you could create immutable class maybe called MaxStringDistance to contain those 3 numbers and instead of returning String, you return something like new MaxStringDistance(first, second, max).
  • Now you are missing String representation, that you previously wanted. One way would be to override toString of your new class so that you can then just print that object to get same results as original code or create another method, that will construct the String (I think within that object is best place for it).
  • You can argue, that method is now "constructing" your MaxStringDistance object. Then it makes sense to put this static method inside MaxStringDistance method as "factory method". Not sure about the name.
  • Parameter name "s" is short and not very descriptive, try to name variables so that it clearly states what does it contain. It's true, that in this case there's not much to say about it.

  That is what I'd do regarding refactoring _b method just based on it's name and signature.

Now let's take a look at _c

• This method is definitely not printing anything, but returning int. This one really needs renaming, probably something like calcualteCharDistance
• Again single character parameters. I'd at least rename "j" to "position" because it seems like it represents character position in the string (+1 so that's why "position", not "index")
• You probably won't be calling this method from anywhere else and can be set it's visibility to private.

Somewhat improved code will look like this:

public class MaxStringDistance {
    private final int first;
    private final int second;
    private final int max;

    //possibly private constructor
    public MaxStringDistance(int first, int second, int max) {
        this.first = first;
        this.second = second;
        this.max = max;
    }

    //getters if needed

    @Override
    public String toString() {
        return first + " " + second + " " + max;
    }

    public static MaxStringDistance fromString(String s) {
        int first = 0;
        int second = 0;
        int max = 0;
        for (int i = 0; i < s.length(); i++) {
            int cur = calculateCharDistance(s, s.charAt(i), i + 1);
            if (cur > max) {
                first = i;
                second = i + cur;
                max = cur;
            }
        }
        return new MaxStringDistance(first, second, max);
    }

    private static int calculateCharDistance(String s, char c, int position) {
        for (int i = position; i < s.length(); i++) {
            if (c == s.charAt(i)) {
                return i - (position - 1);
            }
        }
        return 0;
    }

    public static void main(String[] args) {
        String userInput = new Scanner(System.in).nextLine();
        System.out.println(MaxStringDistance.fromString(userInput));
    }
}

Answer 2

In my opinion, I prefer the first version of it (A); since the code is short.

Here are some recommendations for this version.

1) Uses the java.lang.String#toCharArray and iterate on this, instead of using java.lang.String#charAt; this will make the code shorter and more readable.

2) Extract the s.length() in a variable.

//[...]
final char[] chars = s.toCharArray();
final int lengthOfChars = s.length();

for (int i = 0; i < lengthOfChars; i++) {
    for (int j = i + 1; j < lengthOfChars; j++) {
        if (chars[i] == chars[j]) {
            if ((j - i) > max) {
                first = i;
                second = j;
                max = j - i;
            }
            break;
        }
    }
}
//[...]

3) You can invert the logic and continue the loop if the condition is not valid; I prefer the Guard Clauses in those cases.

//[...]
for (int j = i + 1; j < nbOfChars; j++) {
    if (chars[i] != chars[j] || (j - i) < max) {
        continue;
    }

    first = i;
    second = j;
    max = j - i;
    break;
}
//[...]
```

Answer 3

The question is whether a ("all in one") or b + c ("better abstraction") is better. Better abstraction is generally better, but here one would start with separating logic and printing.

The real advantage of a is the flexibility of coding. To be shown below.

Then there is the naming, c should have a different name. K.H. said it all.

However the code is is better analized in the version a, and could be optimized

/**
 * The maximal distance of the same char at two different positions,
 * with the characters inbetween are different.
 * @param s the text.
 * @return the maximal distance.
 */
public static int maxDistance_a(String s) {
    char[] chs = s.toCharArray();

    int max = 0;
    int maxI = 0;
    // Redundant: int maxJ = 0;

    for (int i = 0; i < chs.length - max; i++) {
        for (int j = i + 1; j < chs.length - max; j++) {
            if (chs[i] == chs[j]) {
                if ((j - i) > max) {
                    max = j - i;
                    maxI = i;
                    // Redundant: maxJ = j;
                }
                break; // No "x...x...x".
            }
        }
    }
    int maxJ = maxI + max;
    logger.info("Max " + max + " at " + maxI + " and " + maxJ);
    return max;
}

As you see the intermediate max found can be used to limit the loops.

public static int maxDistance_a(String s) {
    int max = 0;
    int maxI = 0;

    for (int i = 0; i < s.length() - max; i++) {
        char ch = s.charAt(i);
        int j = s.indexOf(ch, i + 1);
        if (j != -1) {
            if ((j - i) > max) {
                max = j - i;
                maxI = i;
            }
        }
    }
    logger.info("Max " + max + " at " + maxI + " and " + (maxI + max));
    return max;
}

Instead of chars, charAt is still possible, using indexOf. So prematurely introducing a function for the inner loop is not clever.

There is more. You could consider code points instead of chars, as a char is just a UTF-16 value, which for many Unicode code points fits, but is a bit of an abuse.

You could make the text canonical using java.text.Normalizer. A letter with an accent can either be composed to a single Unicode code point, or decomposed as a Unicode Latin letter and a zero-width diacritical mark (accent).