Problem:
 Score : 500 points    Problem Statement Snuke, who loves animals, built a zoo.  There are N animals in this zoo. They are conveniently numbered 1 through N , and arranged in a circle.
The animal numbered i (2≤i≤N-1) is adjacent to the animals numbered i-1 and i+1 . Also, the animal numbered 1 is adjacent to the animals numbered 2 and N , and the animal numbered N is adjacent to the animals numbered N-1 and 1 .  There are two kinds of animals in this zoo: honest sheep that only speak the truth, and lying wolves that only tell lies.  Snuke cannot tell the difference between these two species, and asked each animal the following question: "Are your neighbors of the same species?" The animal numbered i answered s_i . Here, if s_i is o , the animal said that the two neighboring animals are of the same species, and if s_i is x , the animal said that the two neighboring animals are of different species.  More formally, a sheep answered o if the two neighboring animals are both sheep or both wolves, and answered x otherwise.
Similarly, a wolf answered x if the two neighboring animals are both sheep or both wolves, and answered o otherwise.  Snuke is wondering whether there is a valid assignment of species to the animals that is consistent with these responses. If there is such an assignment, show one such assignment. Otherwise, print -1 .      Constraints  3 ≤ N ≤ 10^{5}  s is a string of length N consisting of o and x .         Input The input is given from Standard Input in the following format:  N  s       Output If there does not exist an valid assignment that is consistent with s , print -1 .
Otherwise, print an string t in the following format. The output is considered correct if the assignment described by t is consistent with s .   t is a string of length N consisting of S and W .  If t_i is S , it indicates that the animal numbered i is a sheep. If t_i is W , it indicates that the animal numbered i is a wolf.         Sample Input 1 6
ooxoox      Sample Output 1 SSSWWS  For example, if the animals numbered 1 , 2 , 3 , 4 , 5 and 6 are respectively a sheep, sheep, sheep, wolf, wolf, and sheep, it is consistent with their responses. Besides, there is another valid assignment of species: a wolf, sheep, wolf, sheep, wolf and wolf.  Let us remind you: if the neiboring animals are of the same species, a sheep answers o and a wolf answers x . If the neiboring animals are of different species, a sheep answers x and a wolf answers o .          Sample Input 2 3
oox      Sample Output 2 -1  Print -1 if there is no valid assignment of species.       Sample Input 3 10
oxooxoxoox      Sample Output 3 SSWWSSSWWS

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, S):
    def f(cnd):
        for i in range(1, N):
            if S[i] == 'o' and cnd[i] == 'S':
                cnd.append(cnd[i-1])
            elif S[i] == 'o' and cnd[i] == 'W':
                cnd.append('S' if cnd[i-1] == 'W' else 'W')
            elif S[i] == 'x' and cnd[i] == 'S':
                cnd.append('S' if cnd[i-1] == 'W' else 'W')
            elif S[i] == 'x' and cnd[i] == 'W':
                cnd.append(cnd[i-1])

        cnd.pop()
        for i in range(N):
            if cnd[i] == 'S' and S[i] == 'o':
                if cnd[(i+1) % N] != cnd[i-1]:
                    return None
            elif cnd[i] == 'S' and S[i] == 'x':
                if cnd[(i+1) % N] == cnd[i-1]:
                    return None
            elif cnd[i] == 'W' and S[i] == 'o':
                if cnd[(i+1) % N] == cnd[i-1]:
                    return None
            elif cnd[i] == 'W' and S[i] == 'x':
                if cnd[(i+1) % N] != cnd[i-1]:
                    return None
        return ''.join(cnd)
    
    ans = f(['S', 'S'])
    if ans:
        return ans

    
    ans = f(['S', 'W'])
    if ans:
        return ans

    
    ans = f(['W', 'S'])
    if ans:
        return ans

    
    ans = f(['W', 'W'])
    if ans:
        return ans

    return -1


def main():
    N = read_int()
    S = read_str()
    print(slv(N, S))


if __name__ == '__main__':
    main()

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, S):
    def f(cnd):
        for i in range(1, N):
            if S[i] == 'o' and cnd[i] == 'S':
                cnd.append(cnd[i-1])
            elif S[i] == 'o' and cnd[i] == 'W':
                cnd.append('S' if cnd[i-1] == 'W' else 'W')
            elif S[i] == 'x' and cnd[i] == 'S':
                cnd.append('S' if cnd[i-1] == 'W' else 'W')
            elif S[i] == 'x' and cnd[i] == 'W':
                cnd.append(cnd[i-1])

        cnd.pop()
        for i in range(N):
            if cnd[i] == 'S' and S[i] == 'o':
                if cnd[(i+1) % N] != cnd[i-1]:
                    return None
            elif cnd[i] == 'S' and S[i] == 'x':
                if cnd[(i+1) % N] == cnd[i-1]:
                    return None
            elif cnd[i] == 'W' and S[i] == 'o':
                if cnd[(i+1) % N] == cnd[i-1]:
                    return None
            elif cnd[i] == 'W' and S[i] == 'x':
                if cnd[(i+1) % N] != cnd[i-1]:
                    return None
        return ''.join(cnd)
    
    ans = f(['S', 'S'])
    if ans:
        return ans

    
    ans = f(['S', 'W'])
    if ans:
        return ans

    
    ans = f(['W', 'S'])
    if ans:
        return ans

    
    ans = f(['W', 'W'])
    if ans:
        return ans

    return -1


def main():
    N = read_int()
    S = read_str()
    print(slv(N, S))


if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
s = input()
s += s[0]

is_ans = False
for ans in ['SS', 'SW', 'WS', 'WW']:
    for i in range(1, n+1):
        a_0 = ans[i-1]
        a_1 = ans[i]
        if s[i] == 'o' and a_1 == 'S':
            if a_0 == 'S':
                ans += 'S'
            else:
                ans += 'W'
        elif s[i] == 'x' and a_1 == 'S':
            if a_0 == 'S':
                ans += 'W'
            else:
                ans += 'S'
        elif s[i] == 'o' and a_1 == 'W':
            if a_0 == 'S':
                ans += 'W'
            else:
                ans += 'S'
        else:
            if a_0 == 'S':
                ans += 'S'
            else:
                ans += 'W'
    if ans[-2:] == ans[:2]:
        print(ans[:-2])
        is_ans = True
        break
if not is_ans:
    print(-1)

Solution (Python):
N = int(input())
s = list(input())
c_list = [['W','W'],['W','S'],['S','W'],['S','S']]

for c in c_list:
    for current in range(1,N):
        pre = current-1
        if ((c[current] == 'W' and s[current] == 'o') or (c[current] == 'S' and s[current] == 'x')):
            if(c[pre] == 'W'):
                c.append('S')
            else:
                c.append('W')
        elif ((c[current] == 'W' and s[current] == 'x') or (c[current] == 'S' and s[current] == 'o')):
            c.append(c[pre])
    if(c[0] == c[N]):
        if ((c[0] == 'W' and s[0] == 'o') or (c[0] == 'S' and s[0] == 'x')):
            if(c[1] != c[N-1]):
                print(''.join(c[0:N]))
                quit()
        else:
            if(c[1] == c[N-1]):
                print(''.join(c[0:N]))
                quit()
    """
    if ((c[0] == 'W' and s[0] == 'o') or (c[0] == 'S' and s[0] == 'x')):
        if (c[N-1] != c[1]):
            print(''.join(c[0:N]))
            quit()
    else:
        if (c[N-1] == c[1]):
            print(''.join(c[0:N]))
            quit()
    """
print(-1)

Solution (Python):




N=int(input())
S=input()

def solve(n,s):


  ans="SW"
  if s[0]=="o":
    ch="W"
  else:
    ch="S"
  for i in range(1,n):
    if (ans[-1]=="S" and s[i]=="o") or (ans[-1]=="W" and s[i]=="x") :
      ans = ans + ans[-2]
    elif ans[-1]=="S" and s[i]=="x" and ans[-2]=="S":
      ans = ans + "W"
    elif ans[-1]=="S" and s[i]=="x" and ans[-2]=="W":
      ans = ans + "S"
    elif ans[-1]=="W" and s[i]=="o" and ans[-2]=="S":
      ans = ans + "W"
    else:
      ans = ans + "S"
  if ans[-2]==ch and ans[-1]==ans[0]:
    return ans[:-1]


  ans="WS"
  if s[0]=="o":
    ch="W"
  else:
    ch="S"
    
  for i in range(1,n):
    if (ans[-1]=="S" and s[i]=="o") or (ans[-1]=="W" and s[i]=="x") :
      ans = ans + ans[-2]
    elif ans[-1]=="S" and s[i]=="x" and ans[-2]=="S":
      ans = ans + "W"
    elif ans[-1]=="S" and s[i]=="x" and ans[-2]=="W":
      ans = ans + "S"
    elif ans[-1]=="W" and s[i]=="o" and ans[-2]=="S":
      ans = ans + "W"
    else:
      ans = ans + "S"
  if ans[-2]==ch and ans[-1]==ans[0]:
    return ans[:-1]
  

  ans="SS"
  if s[0]=="o":
    ch="S"
  else:
    ch="W"
    
  for i in range(1,n):
    if (ans[-1]=="S" and s[i]=="o") or (ans[-1]=="W" and s[i]=="x") :
      ans = ans + ans[-2]
    elif ans[-1]=="S" and s[i]=="x" and ans[-2]=="S":
      ans = ans + "W"
    elif ans[-1]=="S" and s[i]=="x" and ans[-2]=="W":
      ans = ans + "S"
    elif ans[-1]=="W" and s[i]=="o" and ans[-2]=="S":
      ans = ans + "W"
    else:
      ans = ans + "S"
  if ans[-2]==ch and ans[-1]==ans[0]:
    return ans[:-1]
  

  ans="WW"
  if s[0]=="o":
    ch="S"
  else:
    ch="W"
    
  for i in range(1,n):
    if (ans[-1]=="S" and s[i]=="o") or (ans[-1]=="W" and s[i]=="x") :
      ans = ans + ans[-2]
    elif ans[-1]=="S" and s[i]=="x" and ans[-2]=="S":
      ans = ans + "W"
    elif ans[-1]=="S" and s[i]=="x" and ans[-2]=="W":
      ans = ans + "S"
    elif ans[-1]=="W" and s[i]=="o" and ans[-2]=="S":
      ans = ans + "W"
    else:
      ans = ans + "S"
  if ans[-2]==ch and ans[-1]==ans[0]:
    return ans[:-1]
  
  return -1

print(solve(N,S))

Solution (Python):


















''' 二次元配列を一列ずつ
for i in ans:
	print(*i)
'''
''' heapq
queue = []
heapq.heapify(queue) 
heapq.heappush(queue,num) 
pop = heapq.heappop(queue) 
pop = heapq.heappushpop(queue,num) 

'''

from collections import defaultdict
import sys,heapq,bisect,math,itertools,string
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7


N = int(input())
s = input()
s = s + s[0]

def check(SW):
	global N
	global s
	for i in range(1,N+1):
		if SW[i]:
			if s[i] == 'o':
				SW.append(SW[i-1])
			else:
				SW.append(not SW[i-1])
		else:
			if s[i] == 'o':
				SW.append(not SW[i-1])
			else:
				SW.append(SW[i-1])

	if SW[N] == SW[0] and SW[N+1] == SW[1]:
		for i in range(N):
			if SW[i]:
				sys.stdout.write("S")
			else:
				sys.stdout.write("W")
		print()
		sys.exit()

check([True,True])
check([True,False])
check([False,True])
check([False,False])
print(-1)

Solution (Python):
n=int(input())
s=list(input())

a=[0]*n

for i in range(n):
    if s[i]=="o":
        a[i]=1
    else:
        a[i]=-1

ans=[0]*n

flag=-1
S=["0"]*n

ans[0]=1
ans[1]=1

for i in range(2,n):
    ans[i]=a[i-1]*ans[i-1]*ans[i-2]
else:
    c1=a[0]*ans[0]*ans[n-1]
    c2=a[n-1]*ans[n-1]*ans[n-2]
    if c1==ans[1] and c2==ans[0]:
        flag=1
        for i in range(n):
            if ans[i]==1:
                S[i]="S"
            else:
                S[i]="W"
        print(''.join(S))

if flag<0:

    ans[0]=-1
    ans[1]=1

    for i in range(2,n):
        ans[i]=a[i-1]*ans[i-1]*ans[i-2]
    else:
        c1=a[0]*ans[0]*ans[n-1]
        c2=a[n-1]*ans[n-1]*ans[n-2]
        if c1==ans[1] and c2==ans[0]:
            flag=1
            for i in range(n):
                if ans[i]==1:
                    S[i]="S"
                else:
                    S[i]="W"
            print(''.join(S))

if flag<0:

    ans[0]=1
    ans[1]=-1

    for i in range(2,n):
        ans[i]=a[i-1]*ans[i-1]*ans[i-2]
    else:
        c1=a[0]*ans[0]*ans[n-1]
        c2=a[n-1]*ans[n-1]*ans[n-2]
        if c1==ans[1] and c2==ans[0]:
            flag=1
            for i in range(n):
                if ans[i]==1:
                    S[i]="S"
                else:
                    S[i]="W"
            print(''.join(S))

if flag<0:

    ans[0]=-1
    ans[1]=-1

    for i in range(2,n):
        ans[i]=a[i-1]*ans[i-1]*ans[i-2]
    else:
        c1=a[0]*ans[0]*ans[n-1]
        c2=a[n-1]*ans[n-1]*ans[n-2]
        if c1==ans[1] and c2==ans[0]:
            flag=1
            for i in range(n):
                if ans[i]==1:
                    S[i]="S"
                else:
                    S[i]="W"
            print(''.join(S))

if flag<0:
    print(flag)

Solution (Python):
from itertools import product

N = int(input())
S = input()


def r(x):
    if x == 'S':
        return 'W'
    else:
        return 'S'


def f(x1, x2, s):
    if s == 'o':
        if x1 == 'S':
            return x2
        else:
            return r(x2)
    else:
        if x1 == 'S':
            return r(x2)
        else:
            return x2


ans = ['-1']
for x1, x2 in product('SW', repeat=2):
    res = [x1, x2]
    for i in range(N):
        x1, x2 = x2, f(x1, x2, S[i])
        res.append(x2)
    if res[:2] == res[-2:]:
        ans = res[1:-1]
        break
print(''.join(ans))

Solution (Python):
n = int(input())
S = input()

def rev(anim):
    if anim == 'S':
        return 'W'
    else:
        return 'S'

def check(comb, ans):
    if comb[1] == 'S':
        if ans == 'o':
            return comb[0] == comb[2]
        else:
            return comb[0] != comb[2]
    else:
        if ans == 'o':
            return comb[0] != comb[2]
        else:
            return comb[0] == comb[2]

import sys
for T in ('SS', 'SW', 'WS', 'WW'):
    for i in range(2, n):
        ans = S[i-1]
        anim = T[i-1]
        prev = T[i-2]
        if ans == 'o':
            if anim == 'S':
                T += prev
            else:
                T += rev(prev)
        else:
            if anim == 'S':
                T += rev(prev)
            else:
                T += prev
    comb1 = T[n-2]+T[n-1]+T[0]
    ans1 = S[n-1]
    comb2 = T[n-1]+T[0]+T[1]
    ans2 = S[0]
    if check(comb1, ans1) and check(comb2, ans2):
        print(T)
        sys.exit(0)
print(-1)

Solution (Python):
N = int(input())
s = input()
animals = ['SS', 'SW', 'WS', 'WW']
for i, animal in enumerate(animals):
  for j in range(N):
    a = 1 if animals[i][-1] == 'S' else -1
    b = 1 if animals[i][-2] == 'S' else -1
    c = 1 if s[(j + 1) % N] == 'o' else -1
    animals[i] += 'S' if a * b * c > 0 else 'W'
ans = -1
for animal in animals:
  if animal[:2] == animal[-2:]:
    ans = animal[:N]
print(ans)

Solution (Python):
N = int(input())
s = input()

def next(p, c, s):
    if p == 'S' and c == 'S':
        return 'S' if s == 'o' else 'W'
    elif p == 'S' and c == 'W':
        return 'W' if s == 'o' else 'S'
    elif p == 'W' and c == 'S':
        return 'W' if s == 'o' else 'S'
    elif p == 'W' and c == 'W':
        return 'S' if s == 'o' else 'W'
    else:
        return None

flag = False
for p, c in [('S', 'S'), ('S', 'W'), ('W', 'S'), ('W', 'W')]:
    r = p + c
    for i in range(1, N-1):
        r += next(r[-2], r[-1], s[i])

    if next(r[-2], r[-1], s[N-1]) == r[0] and next(r[-1], r[0], s[0]) == r[1]:
        flag = True
        print(r)
        break

if not flag:
    print(-1)

Solution (Python):
import math
n = int(input())
s = input()

m = {
  'S': {
    'S': {'o': 'S', 'x': 'W'},
    'W': {'o': 'W', 'x': 'S'},
  },
  'W': {
    'S': {'o': 'W', 'x': 'S'},
    'W': {'o': 'S', 'x': 'W'},
  }
}
import itertools
for p, c in itertools.product(['S','W'], ['S','W']):
  ans = [p, c]
  for a in s:
    p,c = c, m[p][c][a]
    ans.append(c)
  if ans[:2] == ans[-2:]:
    print(''.join(ans[1:-1]))
    exit(0)
print(-1)

Solution (Python):
import copy
n = int(input())
s = list(input())

def search_pattern(input_list):
    temp = copy.deepcopy(input_list)
    for i in range(2, n):
        if temp[i - 1] == 'S':
            if s[i - 1] == 'o':
                temp.append(temp[i - 2])
            else:
                if temp[i - 2] == 'S':
                    temp.append('W')
                else:
                    temp.append('S')
        else:
            if s[i - 1] == 'x':
                temp.append(temp[i - 2])
            else:
                if temp[i - 2] == 'S':
                    temp.append('W')
                else:
                    temp.append('S')

    if temp[n - 1] == 'S':
        if s[n - 1] == 'o':
            if temp[n - 2] != temp[0]:
                return -1
        else:
            if temp[n - 2] == 'S':
                if temp[0] == 'S':
                    return -1
            else:
                if temp[0] != 'S':
                    return -1
    else:
        if s[n - 1] == 'x':
            if temp[n - 2] != temp[0]:
                return -1
        else:
            if temp[n - 2] == 'S':
                if temp[0] == 'S':
                    return -1
            else:
                if temp[0] != 'S':
                    return -1

    if temp[0] == 'S':
        if s[0] == 'o':
            if temp[n - 1] != temp[1]:
                return -1
        else:
            if temp[n - 1] == 'S':
                if temp[1] == 'S':
                    return -1
            else:
                if temp[1] != 'S':
                    return -1
    else:
        if s[0] == 'x':
            if temp[n - 1] != temp[1]:
                return -1
        else:
            if temp[n - 1] == 'S':
                if temp[1] == 'S':
                    return -1
            else:
                if temp[1] != 'S':
                    return -1
    print("".join(temp))
    exit()

search_pattern(list("SS"))
search_pattern(list("SW"))
search_pattern(list("WS"))
search_pattern(list("WW"))

print("-1")

Solution (Python):
import sys
N = int(input())
s = input()
r = ['SS', 'SW', 'WS', 'WW']
flag = [False, False]
for _i in range(4):
    for _j in range(1, N-1):
        if (s[_j] == 'o' and r[_i][_j] == 'S') or (s[_j] == 'x' and r[_i][_j] == 'W'):
            r[_i] += r[_i][_j-1]
        else:
            if r[_i][_j] == 'W':
                if r[_i][_j-1] == 'S':
                    r[_i] += 'W'
                else:
                    r[_i] += 'S'
            if r[_i][_j] == 'S':
                if r[_i][_j-1] == 'W':
                    r[_i] += 'S'
                else:
                    r[_i] += 'W'
    if (s[N-1] == 'o' and r[_i][N-1] == 'S') or (s[N-1] == 'x' and r[_i][N-1] == 'W'):
        if r[_i][N-2] == r[_i][0]:
            flag[0] = True
    else:
        if r[_i][N-2] != r[_i][0]:
            flag[0] = True
    if flag[0]:
            if (s[0] == 'o' and r[_i][0] == 'S') or (s[0] == 'x' and r[_i][0] == 'W'):
                if r[_i][N-1] == r[_i][1]:
                    flag[1] = True
            else:
                if r[_i][N-1] != r[_i][1]:
                    flag[1] = True
    if flag[0] and flag[1]:
        print(r[_i])
        break
    else:
        flag = [False, False]
if not(flag[0]) and not(flag[1]):
    print(-1)

Solution (Python):
N = int(input())
S = input()
for p in ("SS", "SW", "WS", "WW"):  
    ans = p[1]
    ip = p
    for i in range(N):
        if S[i] == "o":
            if p[0] == p[1]:
                p = p[1] + "S"
            else:
                p = p[1] + "W"
        else:
            if p[0] == p[1]:
                p = p[1] + "W"
            else:
                p = p[1] + "S"
        ans += p[-1]
    if ans[-2:] == ip:
        print(ans[:-1])
        exit()
print(-1)

Solution (Python):
N=int(input())
s=input()
animals = ["" for _ in range(N)]

def convert(animal):
    if animal == "S":
        return "W"
    else:
        return "S"

def animalOnRight(left,center,sig):
    if center == "S":
        if sig == "o":
            return left
        else:
            return convert(left)
    else:
        if sig == "o":
            return convert(left)
        else:
            return left
for (a0,a1) in [("W","S"),("W","W"),("S","S"),("S","W")]:
    animals[0],animals[1] = (a0,a1)
    for i in range(N-2):
        animals[i+2] = animalOnRight(animals[i],animals[i+1],s[i+1])
        
    satisfied = (animalOnRight(animals[N-2],animals[N-1],s[N-1]) == animals[0]) and (animalOnRight(animals[N-1],animals[0],s[0]) == animals[1])
    if satisfied:
        for char in animals:
            print(char, end='')
        print()
        exit()
print(-1)

Solution (Python):
N = int(input())
S = input()

B = {"S":"W", "W":"S"}
def check(a0, a1):
    b0,b1 = a0,a1
    A = a1
    for i in range(N):
        if a1 == "S":
            if S[i] == "o":
                a2 = a0
            else:
                a2 = B[a0]
        else:
            if S[i] == "o":
                a2 = B[a0]
            else:
                a2 = a0
        A += a2
        a0,a1 = a1,a2
    if A[0] == A[N] and A[0] == b1 and A[N-1] == b0:
        return A[0:N]
    else:
        return -1

Ans = []
Ans.append(check("S","S"))
Ans.append(check("S","W"))
Ans.append(check("W","S"))
Ans.append(check("W","W"))

for ans in Ans:
    if ans == -1:
        continue
    else:
        print(ans)
        exit()
else:
    print(-1)

Solution (Python):



N = int(input())
s = list(input())

def decide_i_plus_one(p, c, res):
  if c == 'S':
    if res == 'o':
      return p
    else:
      if p == 'S': return 'W'
      else:        return 'S'
  else:
    if res == 'o':
      if p == 'S': return 'W'
      else:        return 'S'
    else:
      return p

def valid(animals):
  
  if decide_i_plus_one(animals[-2], animals[-1], s[-1]) != animals[0]:
    return 0
  
  if decide_i_plus_one(animals[1], animals[0], s[0]) != animals[-1]:
    return 0

  
  return 1

possible_pairs = [('S','S'), ('S','W'), ('W','S'), ('W','W')]
for (fst,snd) in possible_pairs:
  animals = []
  animals.append(fst)
  animals.append(snd)

  pi,ci = 0,1

  while 1:
    if ci == N-1:
      if valid(animals):
        print("".join(animals))
        exit(0)
      else:
        break

    n = decide_i_plus_one(animals[pi], animals[ci], s[ci])

    animals.append(n)
    pi += 1
    ci += 1

print("-1")

Solution (Python):
N = int(input())
s = input()

def makeans(ans):
        for c in s:
                if (ans[-1] == "S") ^ (c == "o") ^ (ans[-2] == "W"):
                        ans += "W"
                else:
                        ans += "S"

        return ans

for initial in ["SS","SW","WS","WW"]:
        ans = makeans(initial)
        if ans[0] == ans[-2] and ans[1] == ans[-1]:
                print(ans[1:-1])
                exit()

print("-1")

Solution (Python):
from itertools import product
N = int(input())
S = input()

C = product("SW", repeat=2)


for c in C:
    ans = list(c)
    for i in range(1, len(S)):
        
        if ans[-1] == "S":
            
            if S[i] == "o":
                ans.append(ans[-2])
            else:
                
                if ans[-2] == "S":
                    ans.append("W")
                else:
                    ans.append("S")
        
        else:
            
            if S[i] == "x":
                ans.append(ans[-2])
            
            else:
                if ans[-2] == "S":
                    ans.append("W")
                else:
                    ans.append("S")

    ans = ans[:-1]
    for i in range(N):
        if ans[i] == "S" and S[i] == "o":
            if ans[i-1] != ans[(i+1) % N]:
                break
        if ans[i] == "S" and S[i] == "x":
            if ans[i-1] == ans[(i+1) % N]:
                break
        if ans[i] == "W" and S[i] == "x":
            if ans[i-1] != ans[(i+1) % N]:
                break
        if ans[i] == "W" and S[i] == "o":
            if ans[i-1] == ans[(i+1) % N]:
                break
    else:
        print("".join(ans))
        break

else:
    print(-1)

Solution (Python):
def check(listx,s):
	num = (listx[-2]+listx[1])%2
	if num!=listx[0] and s[0]=="o": return True
	elif num==listx[0] and s[0]=="x": return True
	else: return False
n = int(input())
s = input()
x,flag,ans = [[1,1],[1,0],[0,1],[0,0]],False,""
for i in range(4):
	for j in range(1,n):
		if (s[j]=="o" and x[i][-1]==1) or (s[j]=="x" and x[i][-1]==0): x[i].append(x[i][-2])
		else: x[i].append(1-x[i][-2])
	if x[i][0]==x[i][-1] and check(x[i],s):
		flag = True
		break
if flag:
	for k in x[i][:n]:
		if k==1: ans+="S"
		else: ans+="W"
	print(ans)
else: print(-1)

Solution (Python):
n = int(input())
s = list(input())
t = [0] * n


def check(one, two):
    t[0: 2] = [one, two]
    for i in range(n - 2):
        if (s[i + 1] == "o" and t[i + 1] == 0) or (s[i + 1] == "x" and t[i + 1] == 1):
            t[i + 2] = t[i]
        else:
            t[i + 2] = 1 - t[i]
    
    a = ((s[-1] == "o" and t[-1] == 0) or (s[-1] == "x" and t[-1] == 1)) and t[-2] == t[0]
    b = ((s[-1] == "o" and t[-1] == 1) or (s[-1] == "x" and t[-1] == 0)) and t[-2] != t[0]
    c = ((s[0] == "o" and t[0] == 0) or (s[0] == "x" and t[0] == 1)) and t[-1] == t[1]
    d = ((s[0] == "o" and t[0] == 1) or (s[0] == "x" and t[0] == 0)) and t[-1] != t[1]
    if (a or b) and (c or d):
        return t
    else:
        return None
    
def sw(t):
    ans = []
    for i in range(n):
        if t[i] == 0:
            ans.append("S")
        else:
            ans.append("W")
    return("".join(ans))





if check(0, 0) is not None:
    print(sw(check(0, 0)))
elif check(0, 1) is not None:
    print(sw(check(0, 1)))
elif check(1, 0) is not None:
    print(sw(check(1, 0)))
elif check(1, 1) is not None:
    print(sw(check(1, 1)))
else:
    print(-1)

Solution (Python):


N = int(input())
statements = list(str(input()))
patterns = [['S', 'S'], ['S', 'W'], ['W', 'S'], ['W', 'W']]
null_flg = 1

for pattern in patterns:
    animals = pattern
    for index in range(1, N-1):
        rule = statements[index] + animals[index]
        if rule == 'oS':
            animals.append(animals[index - 1])
        elif rule == 'xS':
            if animals[index - 1] == 'S':
                animals.append('W')
            else:
                animals.append('S')
        elif rule == 'oW':
            if animals[index - 1] == 'S':
                animals.append('W')
            else:
                animals.append('S')
        elif rule == 'xW':
            animals.append(animals[index - 1])

    last_flg = first_flg = 0
    last = statements[-1] + animals[-1]
    if last == 'oS':
        if animals[0] == animals[-2]:
            last_flg = 1
    elif last == 'xS':
        if animals[0] != animals[-2]:
            last_flg = 1
    elif last == 'oW':
        if animals[0] != animals[-2]:
            last_flg = 1
    elif last == 'xW':
        if animals[0] == animals[-2]:
            last_flg = 1

    if last_flg:
        first = statements[0] + animals[0]
        if first == 'oS':
            if animals[-1] == animals[1]:
                print(''.join(animals))
                null_flg = 0
                break
        elif first == 'xS':
            if animals[-1] != animals[1]:
                print(''.join(animals))
                null_flg = 0
                break
        elif first == 'oW':
            if animals[-1] != animals[1]:
                print(''.join(animals))
                null_flg = 0
                break
        elif first == 'xW':
            if animals[-1] == animals[1]:
                print(''.join(animals))
                null_flg = 0
                break

if null_flg:
    print('-1')

Solution (Python):
def d_menagerie(N, S):
    s = S + S[0:2]  
    for ans in ['SS', 'SW', 'WS', 'WW']:  
        for i in range(1, N + 1):
            if (ans[-1] == 'S' and s[i] == 'o') or (ans[-1] == 'W' and s[i] == 'x'):
                
                
                ans += ans[-2]
            else:
                
                ans += ('S' if ans[-2] == 'W' else 'W')
        if ans[:2] == ans[N:]:
            
            
            ans = ans[:N]
            break
    else:  
        ans = '-1'
    return ans

N = int(input())
S = input().strip()
print(d_menagerie(N, S))

Solution (Python):
N = int(input())
ori1 = [0 for x in  range(N)]
fini = 0
s = input()

init = [[1,1],[1,-1],[-1,1],[-1,-1]]


for it in init:
    flag = 0
    ori = ori1.copy()
    ori[0] = it[0]
    ori[1] = it[1]
    for i in range(N):
        if i == 0:
            continue
        if ori[i] == 1:
            if s[i] == "o":
                if i == N-1:
                    if ori[0] != ori[i-1]:
                        flag = 1

                else:
                    ori[i+1] = ori[i-1]
            else:
                if i == N-1:
                    if ori[0] != -ori[i-1]:
                        flag = 1
                else:
                    ori[i+1] = -ori[i-1]
        else:
            if s[i] == "x":
                if i == N-1:
                    if ori[0] != ori[i-1]:
                        flag = 1
                else:
                    ori[i+1] = ori[i-1]
            else:
                if i == N-1:
                    if ori[0] != -ori[i-1]:
                        flag = 1
                else:
                    ori[i+1] = -ori[i-1]
    if ori[0] == 1:
        if s[0] == "o":
            if ori[1] != ori[-1]:
                flag = 1
        else:
            if ori[1] == ori[-1]:
                flag = 1
    else:
        if s[0] == "x":
            if ori[1] != ori[-1]:
                flag = 1
        else:
            if ori[1] == ori[-1]:
                flag = 1

    if flag == 0:
        ori = ["S" if x == 1 else "W" for x in ori]
        out = ""
        for o in ori:
            out += o
        print(out)
        fini = 1
        break
    else:
        continue

if fini == 0:
    print(-1)