Count the number of cyclic words in an input

Question

Cyclic Words

Problem Statement

We can think of a cyclic word as a word written in a circle. To represent a cyclic word, we choose an arbitrary starting position and read the characters in clockwise order. So, "picture" and "turepic" are representations for the same cyclic word.

You are given a String[] words, each element of which is a representation of a cyclic word. Return the number of different cyclic words that are represented.

I have included my attempt below, and I'm not sure whether to be pleased with it or not (because I'm new to algos). I want to solve this problem in the most efficient way, preferably in an imperative language such as Java.

I would appreciate criticism of my code in terms of both function and form.

private static int countCyclicWords(String[] input) {
    HashSet<String> hashSet = new HashSet<String>();
    String permutation;
    int count = 0;

    for (String s : input) {
        if (hashSet.contains(s)) {
            continue;
        } else {
            count++;
            for (int i = 0; i < s.length(); i++) {
                permutation = s.substring(1) + s.substring(0, 1);
                s = permutation;
                hashSet.add(s);
            }
        }
    }

    return count;
}

Answer 1

There's one trick which you can use to get a reduction in memory usage which is very worthwhile if the strings are long. String.substring returns a new String object but wrapping the same underlying char[] as the original. So your code:

        for (int i = 0; i < s.length(); i++) {
            permutation = s.substring(1) + s.substring(0, 1);
            s = permutation;
            hashSet.add(s);
        }

could be replaced with

        String dbl = s + s;
        for (int i = 0; i < s.length(); i++) {
            hashSet.add(dbl.substring(i, i + s.length()));
        }

and will contain the same strings but only store 2 * s.length() characters rather than s.length() * s.length().

---

The next trick to consider using would be a CharSequence implementation which wraps the original string and an offset for the starting character.

---

Finally, you could consider normalising each cyclic word. Given the s.length() possible rotations, choose the lexicographically smallest and insert only that one into the set. Whether this gives an efficiency improvement will depend on the statistics of the strings, but if they're random and of a length comparable to the size of the alphabet then a naïve algorithm for finding the smallest will be essentially linear, and you gain two things: firstly, the set becomes smaller (less memory usage, faster lookups); and secondly, you can drop count because the number of cyclic words will be just the size of the set.