Calculating Garland Degree of String

Question

Purpose

A garland word is a word

formed by chopping off the last few letters and “wrapping around” to the start.

For example: You can chop off the the trailing “on” from “onion” and still form the word by wrapping around to the starting “on”. In other words, you can write the letters “o”, “n”, “i” in a circle, in that order, and form the word “onion”.

I say that a garland word is of degree n if you can do the above with the last n letters of the word.

Build an implementation that returns the garland degree of a String. (Note, this was a dailyprogrammer subreddit question)

Strategy

• Check if String is size 0 (return garland degree of 0) or size 1 (return garland degree of 1).
• Start with the first character in the String. Iterate through the characters in the String from the second character onwards. Do we see a matching character? If not, return size 0.
• Move on to the first + second characters in the String. Iterate through the characters in the String from the 3rd character onwards for a matching substring - if we can't see one, return size 1.
• Repeat.
• Note that the upper limit of the garland degree should be the the floor of the length of the String divided by 2. (Right? Or am I missing something?)

Implementation

public class GarlandDegreeIdentifierImpl implements GarlandDegreeIdentifier {
    @Override
    public int identifyGarlandDegree(final String candidate) {
        switch (candidate.length()) {
            case 0: {
                return 0;
            }

            case 1: {
                return 1;
            }

            default: {
                final char[] chars = candidate.toCharArray();
                for (int subStringIndex = 1; subStringIndex <= chars.length - subStringIndex; subStringIndex++) {
                    final char[] startingChars = Arrays.copyOfRange(chars, 0, subStringIndex);
                    final char[] remainingChars = Arrays.copyOfRange(chars, subStringIndex, chars.length);
                    if (subsetIndexIdentifier(remainingChars, startingChars) == -1) {
                        return subStringIndex - 1;
                    }
                }

                return Math.floorDiv(chars.length, 2);
            }
        }
    }

    @Override
    public int subsetIndexIdentifier(final char[] chars, final char[] candidateChars) {
        for (int index = 0; index <= chars.length - candidateChars.length; index++) {
            int counter = 0;
            for (int candidateCharIndex = 0; candidateCharIndex < candidateChars.length; candidateCharIndex++) {
                if (chars[index + candidateCharIndex] != candidateChars[candidateCharIndex]) {
                    counter++;
                }
            }

            if (0 == counter) {
                return index;
            }
        }

        return -1;
    }
}

Answer 1

You are completely over-doing it. Your algorithm will be O(n³) (I think) on the length of the input when you can do it more simply in O(n²).

Consider the following instead:

• Start at the middle of the input.
• While the substring starting from this index is not equal the substring beginning the start of the input with the same length, we increment the index.
• Finally, we return the length of the final substring that matched.

Basically, the logic can be summed up by this drawing:

-------------
^^^^^^ ^^^^^^ matches or not?

// if no continue

-------------
^^^^^   ^^^^^ matches or not?

// if no continue

-------------
^^^^     ^^^^ matches or not?

You can see the logic.

Implemented in code, it would be the following:

private static int identifyGarlandDegree(String candidate) {
    int length = candidate.length();
    int index = length / 2;
    while (!candidate.substring(0, length - index).equals(candidate.substring(index))) {
        index++;
    }
    return length - index;
}

Note that we don't need to add a check on index: it won't go out of bounds since when index == length, it will exit normally (empty string being equal to another empty string).

Answer 2

Critique

• Avoid special cases if they aren't necessary. This algorithm handles an empty string just fine. Note that when you consider this code, you are confronted with a philosophical question: what is the garland degree of a word of length 1 (or more generally, what is the degree of a word that consists solely of one repeated character)?

  By my interpretation, "aaaaa" is of degree 4: if you chop off the last four characters, the remaining one-character garland can regenerate "aaaaa". In my view, it can't be of degree 5, because there wouldn't be anything left in the garland.

  Your code reports that "aaaaa" is of degree 2. You seem to have introduced a rule that you can't chop off more than half the word. (I personally don't agree with that rule, but I can understand that interpretation.) However, if that is your interpretation, then how do you justify the special case that a word of length 1 is of degree 1? Your special case seems inconsistent.

• What do you mean by candidate? I would just name the parameter word.
• subsetIndexIdentifier() appears to be a helper function, so it should be private, and not part of your interface. (And why do you need to implement an interface anyway?)

• Avoid using array operations when there are String operations that would work just fine.

  Granted, taking successive substrings is not the most efficient approach, especially in Java ≥ 7. You could avoid making copies by writing your own loops to compare characters within the original string or in a char[] representation of the string. But the code you wrote isn't any more efficient — it also creates many subarrays.

Suggested solution

I would recommend a solution similar to @Tunaki's, but simplified further by using String.startsWith(), and written using a for-loop.

public class GarlandWord {
    public static int degree(String word) {
        for (int i = 1; i < word.length(); i++) {
            if (word.startsWith(word.substring(i))) {
                return word.length() - i;
            }
        }
        return 0;
    }
}