Tejav
#3320

Count The Number of Winning Sequences

Hard
StringDynamic Programming
LeetCode ↗

Approaches

💡

Intuition

Time Space

In this approach, we generate all possible sequences Bob can summon and compare their scores against Alice's score. This method is straightforward but inefficient as it explores all combinations.

⚙️

Algorithm

3 steps
  1. 1Step 1: Generate all possible sequences of Bob's moves of length n, ensuring no consecutive moves are the same.
  2. 2Step 2: For each sequence, calculate the scores for both Alice and Bob based on the rules provided.
  3. 3Step 3: Count the sequences where Bob's score is greater than Alice's score.
solution.py32 lines
1# Full working Python code
2from itertools import product
3
4MOD = 10**9 + 7
5
6def countWinningSequences(s):
7    n = len(s)
8    creatures = ['F', 'W', 'E']
9    count = 0
10
11    for sequence in product(creatures, repeat=n):
12        bob_score = 0
13        alice_score = 0
14        for i in range(n):
15            if (s[i] == 'F' and sequence[i] == 'E'):
16                bob_score += 1
17            elif (s[i] == 'W' and sequence[i] == 'F'):
18                bob_score += 1
19            elif (s[i] == 'E' and sequence[i] == 'W'):
20                bob_score += 1
21            elif (sequence[i] == 'F' and s[i] == 'E'):
22                alice_score += 1
23            elif (sequence[i] == 'W' and s[i] == 'F'):
24                alice_score += 1
25            elif (sequence[i] == 'E' and s[i] == 'W'):
26                alice_score += 1
27
28        if bob_score > alice_score:
29            count += 1
30            count %= MOD
31
32    return count

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.