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.

Fastest wins (Big O, where n = number of chars in a string)

  • 3
    \$\begingroup\$ If you're looking for criticism of your code then the place to go is codereview.stackexchange.com . \$\endgroup\$ Commented Jan 17, 2013 at 8:21
  • \$\begingroup\$ Cool. I'll edit for emphasis on the challenge and move the criticism part to code review. Thanks Peter. \$\endgroup\$
    – eggonlegs
    Commented Jan 17, 2013 at 8:31
  • 1
    \$\begingroup\$ What's the winning criteria? Shortest code (Code Golf) or anything else? Are there any limitataions on the form of input and output? Do we need to write a function or a complete program? Does it have to be in Java? \$\endgroup\$
    – ugoren
    Commented Jan 17, 2013 at 12:46
  • 1
    \$\begingroup\$ @eggonlegs You specified big-O - but with respect to which parameter? Number of strings in array? Is string comparison then O(1)? Or number of chars in string or total number of chars? Or anything else? \$\endgroup\$
    – Howard
    Commented Jan 17, 2013 at 14:13
  • 1
    \$\begingroup\$ @dude, surely it's 4? \$\endgroup\$ Commented Jan 17, 2013 at 23:12

8 Answers 8



Here's my solution. I think it might still be O(n2), but I think the average case is much better than that.

Basically it works by normalizing each string so that any rotation will have the same form. For example:

'amazing' -> 'mazinga'
'mazinga' -> 'mazinga'
'azingam' -> 'mazinga'
'zingama' -> 'mazinga'
'ingamaz' -> 'mazinga'
'ngamazi' -> 'mazinga'
'gamazin' -> 'mazinga'

The normalization is done by looking for the minimum character (by char code), and rotating the string so that character is in the last position. If that character occurs more than once, then the characters after each occurrence are used. This gives each cyclic word a canonical representation, that can be used as a key in a map.

The normalization is n2 in the worst case (where every character in the string is the same, e.g. aaaaaa), but most of the time there's only going to be a few occurrences, and the running time will be closer to n.

On my laptop (dual core Intel Atom @ 1.66GHz and 1GB of ram), running this on /usr/share/dict/words (234,937 words with an average length of 9.5 characters) takes about 7.6 seconds.


import sys

def normalize(string):
   # the minimum character in the string
   c = min(string) # O(n) operation
   indices = [] # here we will store all the indices where c occurs
   i = -1       # initialize the search index
   while True: # finding all indexes where c occurs is again O(n)
      i = string.find(c, i+1)
      if i == -1:
   if len(indices) == 1: # if it only occurs once, then we're done
      i = indices[0]
      return string[i:] + string[:i]
      i = map(lambda x:(x,x), indices)
      for _ in range(len(string)):                       # go over the whole string O(n)
         i = map(lambda x:((x[0]+1)%len(string), x[1]), i)  # increment the indexes that walk along  O(m)
         c = min(map(lambda x: string[x[0]], i))    # get min character from current indexes         O(m)
         i = filter(lambda x: string[x[0]] == c, i) # keep only the indexes that have that character O(m)
         # if there's only one index left after filtering, we're done
         if len(i) == 1:
      # either there are multiple identical runs, or
      # we found the unique best run, in either case, we start the string from that
      # index
      i = i[0][0]
      return string[i:] + string[:i]

def main(filename):
   cyclic_words = set()
   with open(filename) as words:
      for word in words.readlines():
         cyclic_words.add(normalize(word[:-1])) # normalize without the trailing newline
   print len(cyclic_words)

if __name__ == '__main__':
   if len(sys.argv) > 1:

Python (3) again

The method I used was to calculate a rolling hash of each word starting at each character in the string; since it's a rolling hash, it takes O(n) (where n is the word length) time to compute all the n hashes. The string is treated as a base-1114112 number, which ensures the hashes are unique. (This is similar to the Haskell solution, but more efficient since it only goes through the string twice.)

Then, for each input word, the algorithm checks its lowest hash to see if it's already in the set of hashes seen (a Python set, thus lookup is O(1) in the set's size); if it is, then the word or one of its rotations has already been seen. Otherwise, it adds that hash to the set.

The command-line argument should be the name of a file that contains one word per line (like /usr/share/dict/words).

import sys

def rollinghashes(string):
    base = 1114112
    curhash = 0
    for c in string:
        curhash = curhash * base + ord(c)
    yield curhash
    top = base ** len(string)
    for i in range(len(string) - 1):
        curhash = curhash * base % top + ord(string[i])
        yield curhash

def cycles(words, keepuniques=False):
    hashes = set()
    uniques = set()
    n = 0
    for word in words:
        h = min(rollinghashes(word))
        if h in hashes:
            n += 1
            if keepuniques:
    return n, uniques

if __name__ == "__main__":
    with open(sys.argv[1]) as words_file:
        print(cycles(line.strip() for line in words_file)[0])


Not sure about the efficiency of this, most likely rather bad. The idea is to first create all possible rotations of all the words, count the values that uniquely represent the strings and select the minimum. That way we get a number that is unique to a cyclic group.
We can group by this number and check the number of these groups.

If n is the number of words in the list and m is the length of a word then calculating the 'cyclic group number' for all the words is O(n*m), sorting O(n log n) and grouping O(n).

import Data.List
import Data.Char
import Data.Ord
import Data.Function

groupUnsortedOn f = groupBy ((==) `on` f) . sortBy(compare `on` f)
allCycles w = init $ zipWith (++) (tails w)(inits w)
wordval = foldl (\a b -> a*256 + (fromIntegral $ ord b)) 0
uniqcycle = minimumBy (comparing wordval) . allCycles
cyclicGroupCount = length . groupUnsortedOn uniqcycle


Decided to start again, now that I understand the rules of the game (I think).

A 10000 word dictionary of unique randomly composed "words" (lower case only) of length 3. In similar fashion other dictionaries were created consisting of strings of length 4, 5, 6, 7, and 8.


gtakes the current version of dictionary to check. The top word is joined with cyclic variants (if any exist). The word and its matches are appended to the output list, out, of processed words. The output words are removed from the dictionary.

g[{wds_,out_}] := 
   t=Table[StringRotateLeft[s, k], {k, StringLength[s]}];

f runs through all words dictionary.


Example 1: actual words

r = f[{"teaks", "words", "spot", "pots", "sword", "steak", "hand"}]

{{"steak", "teaks"}, {"hand"}, {"pots", "spot"}, {"sword", "words"}}

Example 2: Artificial words. Dictionary of strings of length 3. First, timing. Then the number of cycle words.




Timings as a function of word length. 10000 words in each dictionary.


I don't particularly know how to interpret the findings in terms of O. In simple terms, the timing roughly doubles from the three character dictionary to the four character dictionary. The timing increases almost negligibly from 4 through 8 characters.

  • \$\begingroup\$ Can you possibly post a link to the dictionary you used so I can compare against yours? \$\endgroup\$
    – eggonlegs
    Commented Jan 19, 2013 at 11:21
  • \$\begingroup\$ The following link to dictionary.txt should work: bitshare.com/files/oy62qgro/dictionary.txt.html (Sorry about the minute you'll have to wait for the download to begin.) BTW, the file has the 3char, 4char...8char dictionaries all together, 10000 words in each. You'll want to separate them. \$\endgroup\$
    – DavidC
    Commented Jan 19, 2013 at 14:49

This can be done in O(n) avoiding quadratic time. The idea is to construct the full circle traversing the base string twice. So we construct "amazingamazin" as the full circle string to check all cyclic strings corresponding to "amazing".

Below is the Java solution:

public static void main(String[] args){
    //args[0] is the base string and following strings are assumed to be
    //cyclic strings to check 
    int arrLen = args.length;
    int cyclicWordCount = 0;
        System.out.println("Invalid usage. Supply argument strings...");
    }else if(arrLen==1){
        System.out.println("Cyclic word count=0");

    String baseString = args[0];
    StringBuilder sb = new StringBuilder();
    // Traverse base string twice appending characters
    // Eg: construct 'amazingamazin' from 'amazing'
    for(int i=0;i<2*baseString.length()-1;i++)

    // All cyclic strings are now in the 'full circle' string
    String fullCircle = sb.toString();
    System.out.println("Constructed string= "+fullCircle);

    for(int i=1;i<arrLen;i++)
    //Do a length check in addition to contains
        System.out.println("Found cyclic word: "+args[i]);

    System.out.println("Cyclic word count= "+cyclicWordCount);

I don't know if this is very efficient, but this is my first crack.

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)) {
        } else {
            for (int i = 0; i < s.length(); i++) {
                permutation = s.substring(1) + s.substring(0, 1);
                s = permutation;

    return count;


not sure i understand the problem, but this matches the example @dude posted in the comments at least. please correct my surely incorrect analysis.

for each word W in the given N words of the string list, you have to step through all characters of W in the worst case. i have to assume the hash operations are done in constant time.

use strict;
use warnings;

my @words = ( "teaks", "words", "spot", "pots", "sword", "steak", "hand" );

sub count
  my %h = ();

  foreach my $w (@_)
    my $n = length($w);

    # concatenate the word with itself. then all substrings the
    # same length as word are rotations of word.
    my $s = $w . $w;

    # examine each rotation of word. add word to the hash if
    # no rotation already exists in the hash
    $h{$w} = undef unless
      grep { exists $h{substr $s, $_, $n} } 0 .. $n - 1;

  return keys %h;

print scalar count(@words), $/;

Rust, brute force

run it on Rust Playground!

use std::collections::HashSet;
use std::time::Instant;

fn count_cyclic_words(input: &[&str]) -> usize {
    let mut hash_set = HashSet::new();
    let mut count = 0;

    for &s in input.iter() {
        if hash_set.contains(s) {
        } else {
            count += 1;
            let mut permutation = String::from(s);
            for _ in 0..s.len() {
                permutation = format!("{}{}", &permutation[1..], &permutation[0..1]);


fn main() {
    let test_cases = vec![
        vec!["abc", "cab", "bca"],
        vec!["aaa", "aaa", "aaa"],
        vec!["a", "b", "c"],

    for (i, input) in test_cases.iter().enumerate() {
        let start = Instant::now();
        let count = count_cyclic_words(input);
        let duration = start.elapsed();
        println!("Test case {}: count = {}", i + 1, count);
        println!("Time elapsed: {:?}", duration);


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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