Software Programming

Kunuk Nykjaer

Interview-question: How to find all permutations of a given word in a given text? – Java example

with one comment

Write a function (in Java) to find all permutations of a given word that appear in a given text. For example, for word abc and text abcxyaxbcayxycab the function should return abc, bca, cab.

To find a permutation of a string you can use number theory.

There is a method where you can calculate a hash of a string using prime numbers. Every permutation of the same string will give the same hash value. All other string combination which is not a permutation will give some other hash value.

The hash-value is calculated by c1 * p1 + c2 * p2 + … + cn * pn
where ci is a unique value for the current char in the string and where pi is a unique prime number value for the ci char.

Here is the implementation.

// Author: Kunuk Nykjaer
public class Main {
	final static int[] primes = new int[] { 2, 3, 5, 7, 11, 13, 17, 
		19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 
		73, 79, 83, 89, 97, 101, 103, 107, 109, 113 };
	public static void main(String[] args) {		
		final char[] text = "abcxaaabbbccyaxbcayaaaxycab"
		int hash = val(new char[]{'a','b','c'});					
		for (int i = 0; i < text.length - 2; i++) {
			char[] _123 = new char[]{text[i],text[i+1],text[i+2]};			
				System.out.println(new String(_123) );		
	static int p(char c) {
		return primes[(int)c - (int)'a'];
	static int val(char[] cs) {
		p(cs[0])*(int)cs[0] + p(cs[1])*(int)cs[1] + p(cs[2])*(int)cs[2];

The output is: abc bca cab



Written by kunuk Nykjaer

May 25, 2012 at 1:20 pm

Posted in Algorithm, Java

Tagged with

One Response

Subscribe to comments with RSS.

  1. Great post!

    This page was a big help as well since it explains it in detail:


    October 30, 2012 at 11:20 am

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: