The Samantha Clause

We generate all $2^8 = 256$ possible strings that can be obtained by leaving out letters, then check each string to see if it complies with all the rules.

However, this results in counting certain strings twice; e.g. SAHA can be made using either the first or the second A in SAMANTHA.

One way to avoid this is by keeping a list of generated names and discarding duplicates. I use a different strategy: when arriving at the letter A, if I skipped the previous A without including a letter in between, I discard the solution.

Technical detail/trick: The pattern of including/skipping letters is obtained from the bits of $n$ , which runs from $00000000_2$ (empty string) to $11111111_2$ (all of SAMANTHA).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

String s = "SAMANTHA";
int total = 0;

for (int n = 0; n < 256; n++) {
    boolean valid = true;
    boolean had_a = false, skip_a = false, last_a = false;
    int let_count = 0, cons_count = 0;

    for (int i = 0, k = n; i < 8; i++, k /= 2) {
        char c = s.charAt(i);

        if (k%2 == 0) {
            if (c == 'A') skip_a = true;
        }
        else {   
            let_count++;

            if (c == 'A') {
                if (skip_a || last_a) valid = false;
                had_a = true; cons_count = 0;
            }
            else {
                cons_count++; if (cons_count > 3) valid = false;
            }

            skip_a = false; last_a = (c == 'A');
        }
    }

    if (!had_a || let_count < 3) valid = false;

    if (valid) total ++;
}
out.println(total);

Output:

1

128

Solution in python 3.5:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

lst = ['']

for k in "SAMANTHA":
    lst = lst + [x + k for x in lst]

tr = str.maketrans('SMNTH', 'XXXXX')

res = set([x for x in lst if len(x) >= 3 and x.find('A') >= 0 and x.find('AA')==-1 
       and x.translate(tr).find('XXXX') == -1])

print(len(res))