InterviewPractice.java

import java.util.Scanner;

// Takes in a String, and returns all ecryptions:
// i.e. if 'home' is our input string, encryptions would be:
// 4, 3e, h3, h2e, 2me, ho2, h1m1, (etc). 
// No two numbers could be next to each other.

public class InterviewPractice 
{
	public static void main(String[] args)
	{
		Scanner sc = new Scanner(System.in);
		String input = sc.next();

		int length = input.length() - 1;

		// the current value we are at
		int cur = 1 << length+1;

		while (cur >= 0)
		{
			int numZeroes = 0;
			StringBuilder sb = new StringBuilder("");
			for (int i = length; i >= 0; --i)
			{
				// if we found a '1'
				if ((cur & (1 << i)) != 0)
				{

					if (numZeroes > 0)
					{
						sb.append(numZeroes);
						numZeroes = 0;
					}

					// then write the character
					sb.append(input.charAt(length - i));
				}
				else
				{
					++numZeroes;
				}
			}
			if (numZeroes > 0)
			{
				sb.append(numZeroes);
			}
			System.out.println(sb.toString());
			--cur;
		}

	}

}