Rahul is a geek. Head is the lucky call for him. You have to make him lucky. You are provided N coins. If the coin is heads facing upwards it means he is lucky else unlucky, your task is to do an operation to make him lucky. Operation allowed is as follows :
Starting from first element, if you find any coin heads facing downwards (Tail), flip the coin at i^{th} index and (i+1)^{th} index.  
 
Example 1:
Input:
5
H T H T H
Output:
2
2 3
Explanation:
Coins at index 2 and 3 needs to
be flipped to make Rahul happy.
Example 1:
Input:
3
H H H
Output:
0
Explanation:
No index to be flipped.
 
 
Your Task:  
You don't need to read input or print anything. Your task is to complete the function flippedIndexes() which takes the char array A[], its size N and a getAnswer[]  array as inputs and returns the count of the number of indexes to be flipped and stores the indexes in the getAnswer[] array.
Note:- If count is zero, you don't need to store anything in the getAnswer[] array.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
 
Constraints:
1 ≤ N ≤ 10^{7}
A[i] = {'H', 'T'}

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Starter code: #User function Template for python3

class Solution:
    def flippedIndexes(self, a, n, getAnswer):
        # Your code goes here
        
        
        

Solutions:
class Solution:

	def flippedIndexes(self, a, n, getAnswer):
		c = 0
		for i in range(n):
			if a[i] == 'T':
				a[i] = 'H'
				if i + 1 < n:
					if a[i + 1] == 'H':
						a[i + 1] = 'T'
					else:
						a[i + 1] = 'H'
				getAnswer[c] = i + 1
				c += 1
		return c


class Solution:

	def flippedIndexes(self, a, n, getAnswer):
		count = 0
		p = []
		for index in range(n - 1):
			if a[index] == 'T':
				a[index] = 'H'
				a[index + 1] = 'T' if a[index + 1] == 'H' else 'H'
				count += 1
				p.append(index + 1)
		if a[-1] == 'T':
			count += 1
			p.append(n)
		getAnswer[:] = p
		return count


class Solution:

	def flippedIndexes(self, a, n, getAnswer):
		for i in range(n):
			a[i] = int(a[i] == 'T')
		count = 0
		for i in range(n - 1):
			if a[i] % 2:
				getAnswer[count] = i + 1
				a[i + 1] += 1
				count += 1
		if a[-1] % 2:
			getAnswer[count] = n
			count += 1
		return count


class Solution:

	def flippedIndexes(self, arr, n, getAnswer):
		cnt = 0
		flip = 0
		for i in range(n):
			if arr[i] == 'T':
				arr[i] = 'H'
				cnt += 1
				flip += 1
				if i + 1 < n:
					if arr[i + 1] == 'H':
						arr[i + 1] = 'T'
					else:
						arr[i + 1] = 'H'
				getAnswer[flip - 1] = i + 1
		return flip


class Solution:

	def flippedIndexes(self, a, n, getAnswer):
		count = 0
		if a.count('T') == 0:
			return 0
		for i in range(n):
			if a[i] == 'T':
				count += 1
				a[i] = 'H'
				if i + 1 < n:
					if a[i + 1] == 'H':
						a[i + 1] = 'T'
					elif a[i + 1] == 'T':
						a[i + 1] = 'H'
				getAnswer[count - 1] = i + 1
		return count


class Solution:

	def flippedIndexes(self, a, n, getAnswer):
		c = 0
		j = 0
		for i in range(n):
			if a[i] == 'T':
				getAnswer[j] = i + 1
				j += 1
				c += 1
				a[i] = 'H'
				if i < n - 1 and a[i + 1] == 'T':
					a[i + 1] = 'H'
				elif i < n - 1 and a[i + 1] == 'H':
					a[i + 1] = 'T'
		return c


class Solution:

	def flippedIndexes(self, a, n, ans):
		if n == 1:
			if a[0] == 'T':
				ans[0] = 1
				return 1
		c = 0
		for i in range(n - 1):
			if a[i] == 'T':
				ans[c] = i + 1
				c += 1
				if a[i + 1] == 'T':
					a[i + 1] = 'H'
				else:
					a[i + 1] = 'T'
			if i + 1 == n - 1 and a[i + 1] == 'T':
				ans[c] = i + 2
				c += 1
		return c


class Solution:

	def flippedIndexes(self, a, n, g):
		c = 0
		j = 0
		for i in range(n):
			if a[i] == 'T':
				c = c + 1
				g[j] = i + 1
				j = j + 1
				a[i] = 'H'
				if i == n - 1:
					break
				if a[i + 1] == 'H':
					a[i + 1] = 'T'
				else:
					a[i + 1] = 'H'
		return c


class Solution:

	def flippedIndexes(self, a, n, getAnswer):
		c = 0
		for i in range(0, n - 1):
			if a[i] == 'T':
				getAnswer[c] = i + 1
				c += 1
				a[i] = 'H'
				if a[i + 1] == 'H':
					a[i + 1] = 'T'
				elif a[i + 1] == 'T':
					a[i + 1] = 'H'
		if a[n - 1] == 'H':
			return c
		else:
			getAnswer[c] = n
			return c + 1

def main():
	T = int(input())
	while T > 0:
		n = int(input())
		a = [x for x in input().strip().split()]
		getAnswer = [0] * n
		ob = Solution()
		count = ob.flippedIndexes(a, n, getAnswer)
		print(count)
		if count > 0:
			for i in range(count):
				print(getAnswer[i], end=' ')
		else:
			print(-1, end=' ')
		print()
		T -= 1
if __name__ == '__main__':
	main()


class Solution:

	def flippedIndexes(self, arr, n, getAnswer):
		ans = 0
		x = 0
		for i in range(n - 1):
			if arr[i] == 'T':
				arr[i + 1] = 'T' if arr[i + 1] == 'H' else 'H'
				ans += 1
				getAnswer[x] = i + 1
				x += 1
		if arr[n - 1] == 'T':
			ans += 1
			getAnswer[x] = n
		return ans


class Solution:

	def flippedIndexes(self, a, n, getAnswer):
		count = 0
		for (i, s) in enumerate(a):
			if s == 'T':
				getAnswer[count] = i + 1
				count += 1
				if i != n - 1:
					if a[i + 1] == 'T':
						a[i + 1] = 'H'
					else:
						a[i + 1] = 'T'
		return count


class Solution:

	def flippedIndexes(self, a, n, getAnswer):
		count = 0
		ii = 0
		nn = 0
		for i in range(n - 1):
			ii += 1
			if a[i] == 'T':
				a[i] == 'H'
				if a[i + 1] == 'H':
					a[i + 1] = 'T'
				else:
					a[i + 1] = 'H'
				count += 1
				getAnswer[nn] = ii
				nn += 1
		if a[n - 1] == 'T':
			ii += 1
			getAnswer[nn] = ii
			count += 1
		return count


class Solution:

	def flippedIndexes(self, a, n, getAnswer):
		re = []
		ct = 0
		for i in range(n - 1):
			if a[i] == 'T':
				ct += 1
				re.append(i + 1)
				a[i] = 'H'
				if a[i + 1] == 'T':
					a[i + 1] = 'H'
				else:
					a[i + 1] = 'T'
		if a[n - 1] == 'T':
			ct += 1
			re.append(n)
		for j in range(ct):
			getAnswer[j] = re[j]
		return ct


class Solution:

	def flippedIndexes(self, a, n, getAnswer):
		count = 0
		am = 0
		for i in range(n):
			if a[i] == 'T':
				self.flip(a, i)
				try:
					self.flip(a, i + 1)
				except IndexError:
					pass
				count += 1
				getAnswer[am] = i + 1
				am += 1
		return count

	def flip(self, a, i):
		if a[i] == 'H':
			a[i] = 'T'
		else:
			a[i] = 'H'


class Solution:

	def flippedIndexes(self, arr, n, getAnswer):
		count = 0
		j = 0
		for i in range(n - 1):
			if arr[i] == 'T':
				arr[i] = 'H'
				if arr[i + 1] == 'H':
					arr[i + 1] = 'T'
				else:
					arr[i + 1] = 'H'
				count += 1
				getAnswer[j] = i + 1
				j += 1
		if arr[-1] == 'T':
			arr[-1] = 'H'
			getAnswer[j] = n
			count += 1
		return count