-
Notifications
You must be signed in to change notification settings - Fork 3
/
words.py
73 lines (63 loc) · 2.14 KB
/
words.py
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
"""
Problem 3 – Words
You are given a string containing Latin letters. Write a program that finds the number of all words with no two consecutive equal characters that can be generated by reordering the given letters. The generated words should contain all given letters. If the given word meets the requirements it should also be considered in the count.
Input
The input data should be read from the console.
On the only input line there will be a single word containing all the letters that you should use for generating the words.
The input data will always be valid and in the format described. There is no need to check it explicitly.
Output
The output data should be printed on the console.
On the only output line write the number of words found.
Constraints
The number of the given letters will be between 1 and 10, inclusive.
All given letters will be small Latin letters ('a' – 'z')
Allowed working time for your program: 0.35 seconds. Allowed memory: 32 MB.
Examples
Input
Sample Output
Comments
xy
2
Two possible words: "xy" and "yx"
xxxy
0
It is impossible to construct a word with these letters.
aahhhaa
1
The only possible word is "ahahaha".
nopqrstuvw
3628800
There are 3628800 possible words.
"""
from collections import Counter
from math import factorial
def word_is_valid(word):
last_chr = word[0]
for i in range(1, len(word)):
current_chr = word[i]
if last_chr == current_chr:
return False
last_chr = current_chr
return True
valid_words = set()
def permute(a, l, r):
global valid_words
if l == r:
word = ''.join(a)
if word not in valid_words and word_is_valid(word):
valid_words.add(''.join(a))
else:
for i in range(l,r+1):
a[l], a[i] = a[i], a[l]
permute(a, l+1, r)
a[l], a[i] = a[i], a[l] # backtrack
word = input()
word_is_unique = not any(val != 1 for val in Counter(word).values()) # optimization for words with unique letters
if word_is_unique:
print(factorial(len(word)))
else:
permute(list(word), 0, len(word)-1)
if valid_words is not None:
print(len(valid_words))
else:
print(0)