Snakes, Mongooses and the Ultimate Election

 

1. Problem Summary

You’re given a string of length n with characters:

• 's' = snake

• 'm' = mongoose

They stand in a line. Before voting:

• Each mongoose can eat at most one neighboring snake (left or right, indices differ by 1).

• Each snake can be eaten by at most one mongoose.

• Mongooses choose their eating strategy to maximize the number of snakes eaten.

After all eating:

• The remaining snakes each vote for snakes.

• Remaining mongooses each vote for mongooses.

You must decide the winner:

• Print "snakes" if snakes count > mongooses count.

• Print "mongooses" if mongooses count > snakes count.

• Print "tie" otherwise.

Multiple test cases.

Constraints:

• 1≤T≤100

• 1≤∣s∣≤100

2. Examples Explanation

Sample Input:

4

sm

ssm

sms

ssmmmssss

Sample Output:

mongooses

tie

tie

snakes

1. "sm"

• Mongoose at position 2 eats snake at position 1.

• Remaining: 0 snakes, 1 mongoose → "mongooses".

2. "ssm"

• Mongoose at position 3 can eat snake at position 2.

• Remaining: 1 snake (pos1), 1 mongoose (pos3) → "tie".

3. "sms"

• Mongoose (pos2) has two neighboring snakes (pos1 and pos3) but can eat only one.

• Regardless of which it eats, remaining: 1 snake, 1 mongoose → "tie".

4. "ssmmmssss"

• Mongooses can eat at most 2 snakes in an optimal strategy (e.g., s*mmm*sss, * = eaten snake).

• Suppose 2 snakes eaten:

• Initial: snakes = 6, mongooses = 3.

• After eating: snakes = 4, mongooses = 3 → "snakes".

3. Approach

Pattern:

This is a greedy matching on a line problem (like maximum matching in a path graph) where:

• Vertices: animals.

• Edges: mongoose–snake neighbor pairs.

• Each mongoose can be matched to at most one snake; each snake to at most one mongoose.

• Mongooses choose a matching that maximizes eaten snakes.

Naive Idea:

Try all possible ways mongooses can eat snakes:

• Each mongoose has up to 2 choices (left/right/none).

• Brute force would be exponential in worst case → too slow.

We need a linear greedy.

Greedy Strategy:

We want to maximize the number of eaten snakes. Classic approach:

1. Traverse the string left to right.

2. For each mongoose 'm' that hasn’t eaten yet:

• Prefer eating the left neighbor snake if it exists and is uneaten.

• Otherwise, try the right neighbor snake if it exists and is uneaten.

Why left first?
We process from left to right, so:

• When we are at index i, the left neighbor i-1 is already decided for earlier animals.

• If the left neighbor i-1 is a snake and still uneaten, no earlier mongoose could eat it (they’re not adjacent), so we should take it now or lose that option.

• Taking left first ensures we don’t “waste” a chance to eat a snake that no future mongoose can reach.

This greedy approach gives a maximum matching on a path graph, which is known to be optimal.

Algorithm:

• Convert the string to an array.

• Keep a boolean array eaten[] of length n, all false.

• Loop i from 0 to n - 1:

• If s[i] == 'm':

• If i-1 >= 0 and s[i-1] == 's' and not eaten[i-1]:

• eaten[i-1] = true (mongoose eats snake on the left).

• Else if i+1 < n and s[i+1] == 's' and not eaten[i+1]:

• eaten[i+1] = true (mongoose eats snake on the right).

• After this:

• Count snakes that are not eaten: positions where s[i] == 's' and eaten[i] == false.

• Count mongooses: positions where s[i] == 'm'.

• Compare counts to decide "snakes", "mongooses", or "tie".

Edge Cases:

• All snakes: winner "snakes".

• All mongooses: winner "mongooses".

• Single character: trivial based on 's' or 'm'.

Pseudo-code:

Complexity Analysis:

For each string of length n:

• Single pass to assign eatings: O(n).

• Single pass to count remaining animals: O(n).

With ∣s∣≤100 and T≤100, this is easily fast.

Time Complexity: O(n) per test case.

Space Complexity: O(n) for eaten[].

Java code

C code

C++ code

Python code

JavaScript code