TCHS-2-1000

Problem Statement

A spell is defined by its incantation, the word spoken when the spell is being cast. If you know the incantation of a spell, you can create counterspells in the following manner. First, you can optionally delete any number of characters from the original incantation. Note that empty incantations are not valid so you cannot delete all characters. Then, you can replace any number of the remaining characters according to a set of replacement rules. The replacement rules tell you which letters can be replaced, and the letters with which they can be replaced. For example, if the original incantation is "AA" and the allowed replacement is 'A' to 'Z', the following counterspells are possible: "AA", "A", "Z", "ZZ", "AZ", "ZA".

The best counterspell is the one with the greatest power. The power of a spell is the product of all its character values modulo 77077, where the value for a character is its position in the alphabet (character 'A' has value 1, character 'B' value 2, character 'C' value 3, and so on). The best possible counterspell for "AA" in the example above is "ZZ", which has a power of 676.

Please note that if the allowed replacements are 'A' to 'B' and 'B' to 'C', the counterspell for "AB" is "BC" not "CC". You cannot change a character that has already been changed, even if it would lead to a more powerful spell.

You will be given a String spell, the incantation of the spell you are going to counter, and a String rules, the allowed replacements for letters. The first character in rules is the allowed replacement for the letter 'A', the second for 'B' and so on. The character '-' is used to denote a letter that cannot be replaced. Your program must return a String, the most powerful counterspell available. If multiple return values are possible, return the shortest among them. If a tie still exists return the lexicographically earliest.

Definition

Class:	Wizarding
Method:	counterspell
Parameters:	String, String
Returns:	String
Method signature:	String counterspell(String spell, String rules)
(be sure your method is public)

Constraints

-

spell will contain between 1 and 13 characters, inclusive.

-

spell will contain only uppercase letters ('A'-'Z').

-

rules will contain exactly 26 characters.

-

rules will contain only uppercase letters ('A'-'Z') and dashes ('-').

Examples

0)

"AA"

"Z-------------------------"

Returns: "ZZ"

The example from the problem statement.

1)

"AB"

"ZS------------------------"

Returns: "ZS"

The possible counterspells are "AB", "A", "B", "Z", "S", "ZB", "AS" and "ZS".
"ZS" is the most powerful.

2)

"ZZZZ"

"-------------------------Z"

Returns: "ZZZZ"

3)

"ABCDE"

"ZYXXYXZZXYXXZZXZYYXZZZX---"

Returns: "ZXXE"

4)

"ABCDEABCDEABC"

"ACBDESKADSLOEDDDASDBADEDAE"

Returns: "CCDECCECC"

public class Wizarding {

	String spell, rules;
	StringBuilder smax, sb = new StringBuilder();
	int max = -1;

	private int calc(StringBuilder sb) {
		long product = 1;
		for (int i = 0; i < sb.length(); i++)
			product *= (sb.charAt(i) - 'A' + 1);
		return (int) (product % 77077);
	}

	private void choose(int start, int step, int length) {
		if (step == length) {
			int now = calc(sb);
			if (now > max || now == max && sb.length() < smax.length()
					|| now == max && sb.length() == smax.length()
					&& sb.toString().compareTo(smax.toString()) < 0) {
				max = now;
				smax = new StringBuilder(sb);
			}
			return;
		}
		for (int i = start; i < spell.length(); i++) {
			sb.append(spell.charAt(i));
			choose(i + 1, step + 1, length);
			sb.deleteCharAt(sb.length() - 1);
			if (rules.charAt(spell.charAt(i)-'A') == '-')
				continue;
			sb.append(rules.charAt(spell.charAt(i)-'A'));
			choose(i + 1, step + 1, length);
			sb.deleteCharAt(sb.length() - 1);
		}
	}

	public String counterspell(String spell, String rules) {
		this.spell = spell;
		this.rules = rules;
		for (int i = 1; i <= spell.length(); i++)
			choose(0, 0, i);
		return smax.toString();
	}
	
}