Make Them Equal (Codeforces 1594C)
Tags: Math, strings

Theofanis has a string $$$s_1 s_2 \dots s_n$$$ and a character $$$c$$$. He wants to make all characters of the string equal to $$$c$$$ using the minimum number of operations.In one operation he can choose a number $$$x$$$ ($$$1 \le x \le n$$$) and for every position $$$i$$$, where $$$i$$$ is not divisible by $$$x$$$, replace $$$s_i$$$ with $$$c$$$. Find the minimum number of operations required to make all the characters equal to $$$c$$$ and the $$$x$$$-s that he should use in his operations.

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.The first line of each test case contains the integer $$$n$$$ ($$$3 \le n \le 3 \cdot 10^5$$$) and a lowercase Latin letter $$$c$$$ — the length of the string $$$s$$$ and the character the resulting string should consist of.The second line of each test case contains a string $$$s$$$ of lowercase Latin letters — the initial string.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$.

Output: For each test case, firstly print one integer $$$m$$$ — the minimum number of operations required to make all the characters equal to $$$c$$$.Next, print $$$m$$$ integers $$$x_1, x_2, \dots, x_m$$$ ($$$1 \le x_j \le n$$$) — the $$$x$$$-s that should be used in the order they are given.It can be proved that under given constraints, an answer always exists. If there are multiple answers, print any.

Note: Let's describe what happens in the third test case:   $$$x_1 = 2$$$: we choose all positions that are not divisible by $$$2$$$ and replace them, i. e. bzyx $$$\rightarrow$$$ bzbx;  $$$x_2 = 3$$$: we choose all positions that are not divisible by $$$3$$$ and replace them, i. e. bzbx $$$\rightarrow$$$ bbbb. 

Sample Inputs:
3
4 a
aaaa
4 a
baaa
4 b
bzyx

Sample Outputs:
0
1
2
2 
2 3

Solution (Python):
import sys
input = sys.stdin.readline

def solve():
    (n, c) = input().split()
    n = int(n)
    S = input().strip()
    if c * n == S:
        print(0)
        return
    for i in range(n // 2 + 1, n + 1):
        if S[i - 1] == c:
            print(1)
            print(i)
            return
    print(2)
    print(*[n - 1, n])
for _ in range(int(input())):
    solve()

Solution (Python):
import sys
input = sys.stdin.readline
for _ in range(int(input())):
    (n, c) = input().split(' ')
    n = int(n)
    c = c.strip()
    s = input().strip()
    if s == c * n:
        print(0)
    else:
        for index in range(n // 2, n):
            if s[index] == c:
                print(1)
                print(index + 1)
                break
        else:
            print(2)
            print(n, n - 1)

Solution (Python):
import heapq
from collections import Counter
import math
import sys
input = sys.stdin.readline

def inp():
    return int(input())

def inlt():
    return list(map(int, input().split()))

def insr():
    s = input()
    return list(s[:len(s) - 1])

def invr():
    return map(int, input().split())

def inis():
    return input().split()

def SieveOfEratosthenes(n):
    prime = [True for i in range(n + 1)]
    p = 2
    l = []
    while p * p <= n:
        if prime[p] == True:
            for i in range(p * p, n + 1, p):
                prime[i] = False
        p += 1
    for p in range(2, n + 1):
        if prime[p]:
            l.append(p)
    return l

def isPrime(n):
    prime_flag = 0
    if n > 1:
        for i in range(2, int(math.sqrt(n)) + 1):
            if n % i == 0:
                prime_flag = 1
                break
        if prime_flag == 0:
            return True
        else:
            return False
    else:
        return False
for _ in range(inp()):
    (p, c) = inis()
    n = int(p)
    s = insr()
    if s.count(c) == n:
        print(0)
        continue
    for i in range(n // 2, n):
        if s[i] == c:
            print(1)
            print(i + 1)
            break
    else:
        print(2)
        print(n, n - 1)