optimizing

I've recently made a new friend, recursion, and decided to try out some of topcoder's 1000-point problems. Right now, I'm stuck on this problem. I have a working solution but it goes beyond the 2 second limit with the last example.
I've tried looking at other people's code but I can't figure out the logic behind their code.

This is my code, how can I Improve it?

Code:

---

#include <string>
#include <iostream>
#include <vector>

using namespace std;

class Wizarding
{
        string s1; //spell
        int p;    //power
        void cs(string s, string r, std::vector<bool> c)
        {
                int tempp = 1;
                for (int i = 0; i < s.length(); i++)
                        tempp *= (s[i]-'A'+1);
                tempp %= 77077;
                if (tempp > p)
                {
                        this->s1 = s;
                        this->p = tempp;
                }
                {
                        bool a = 0;
                        for (int i = 0; i < c.size(); i++) if (c[i]!= true) {a=true;break;}
                        if (a && s.length() == 1)
                                return;
                }
               
                //replace
                for (int i = 0; i < s.length(); i++)
                {
                        if (c[i])
                                continue;
                        string temps = s;
                        temps[i] = r[s[i]-'A'];
                        c[i] = true;
                        cs(temps, r, c);
                        c[i] = false;
                }
                //remove
                for (int i = 0; s.length()!= 1 && i < s.length(); i++)
                {
                        string temps = s;
                        temps.erase(temps.begin()+i);
                        std::vector<bool> tempc;
                        for (int j = 0; j < c.size(); j++) if (j != i) tempc.push_back(c[j]);
                        cs(temps, r, tempc);
                }
        }
        public:
                string counterspell(string spell, string rules);
};

string Wizarding::counterspell(string spell, string rules)
{
        s1 = spell;
        p = 0;
        std::vector<bool> c(spell.length(), false);
        for (int i = 0; i < spell.length(); i++)
                if (rules[spell[i]-'A'] == '-') c[i] = true;
        cs(spell, rules, c);
        return this->s1;
}

---

The link requires membership. Describe what the program's meant to do.

asdf

Quote:

---

Wizarding

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"

---

I can't be bothered reading over the description of what the code is supposed to do, so I'll just give tips based on what the code does poorly, just by looking at it. As such I might miss higher-level optimisations.

Don't pass everything by value, especially not the vector. Pass everything by reference, or const-reference as appropriate.

"s.length()!= 1 &&" should not be part of the condition in one of your for-loops as s does not change during the loop. Put it in an if-statement surrounding the loop instead.
Given how the vector will only contain relatively few items, you may find it faster to use vector<char> instead, avoiding the vector<bool> specialisation.

With reference to this:

Code:

---

                        if (a && s.length() == 1)
                                return;

---

Why don't you check the length of s against 1 before you even bother to loop through the c vector? In fact you already have some brackets around it, so just put an "if (s.length() == 1)" in front of it and remove it from the later if-statement.

You could premanipulate your strings before calling cs to subtract 'A' from each letter, and then add 'A' back to each char once you have your result. Do this last as it will probably make debugging harder. Or you could prepend a lot of dummy characters to that string, to save the need to subtract 'A' all the time, which would leave everything readable.

There is probably a higher level optimisation opportunity being missed, but I'm not prepared to spend the time to try and understand the problem statement at the moment.

nvm, I think i can find it myself... eventually...
/*Those kinds of changes would only make minor improvements on it's performance, but thanks anyways. I'll keep those in mind for my next project.

I can't copy/paste other people's code so here's a screenshot of one of them. Can someone explain to me the logic behind this code? (it's mainly solve's args that are confusing me)
Attachment 7749*/