You are given an encoded string S of length N. The encoded string is mixed with some number of substring "LIE" and some secret message. You have to extract secret message from it by removing all the "LIE" substrings.
For example - "I AM COOL" is given as "LIEILIEAMLIELIECOOL".
Example 1:
Input: S = "LIEILIEAMLIELIECOOL"
Output: "I AM COOL"
Example 2:
Input: S = "LIELIEALIEBCLIE"
Output: "A BC"
Your Task:  
You don't need to read input or print anything. Your task is to complete the function ExtractMessage() which accepts a string as input parameter and returns a string containing secret message.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ N ≤ 10^{6}
String contains only Upper Case Letters.

Difficulty: EASY
Tags: String algorithms

Data structures
Skill types: Data structures
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)

Starter code:
#User function Template for python3

class Solution:

    def ExtractMessage(self, s):
        # code here

Solutions:
class Solution:

	def ExtractMessage(self, s):
		s = s.split('LIE')
		l = []
		for i in s:
			if i != '':
				l.append(i)
		return ' '.join(l)


class Solution:

	def ExtractMessage(self, s):
		k = s.replace('LIE', ' ')
		k = k.split()
		s1 = ''
		for i in k:
			s1 += i + ' '
		return s1


class Solution:

	def ExtractMessage(self, s):
		a = ''
		s = s.replace('LIE', ' ').split(' ')
		for i in s:
			if i != '':
				a += i + ' '
		return a


import re

class Solution:

	def ExtractMessage(self, s):
		r = s.replace('LIE', ' ').lstrip()
		op = re.sub(' +', ' ', r)
		return op


class Solution:

	def ExtractMessage(self, s):
		s = s.replace('LIE', ' ')
		a = ''
		b = ''
		for i in s:
			if i.isspace() and a != '':
				b += a
				b += ' '
				a = ''
			elif i != ' ':
				a += i
		return b + a


class Solution:

	def ExtractMessage(self, s):
		s = s.split('LIE')
		s = [x for x in s if len(x) > 0]
		return ' '.join(s)


import re

class Solution:

	def ExtractMessage(self, s):
		for i in s:
			r = s.replace('LIE', ' ').lstrip()
			removespaces = re.sub(' +', ' ', r)
			return removespaces


class Solution:

	def ExtractMessage(self, s):
		s = s.split('LIE')
		m = ''
		for i in range(len(s)):
			if s[i] != '':
				m = m + s[i] + ' '
		return m


class Solution:

	def ExtractMessage(self, s):
		msg = ''
		word_list = s.split('LIE')
		for item in word_list:
			if item != '':
				msg += item + ' '
		return msg


class Solution:

	def ExtractMessage(self, s):
		stack = []
		for i in s.replace('LIE', '/').split('/'):
			if i not in '':
				stack.append(i)
		return ' '.join(stack)


import re

class Solution:

	def ExtractMessage(self, s):
		return re.sub(' +', ' ', s.replace('LIE', ' ')).strip()


class Solution:

	def ExtractMessage(self, s):
		result = ' '
		while len(s) > 2:
			if s[:3] == 'LIE':
				s = s[3:]
				if result[-1] != ' ':
					result += ' '
			else:
				result += s[0]
				s = s[1:]
		return (result + s).strip()


class Solution:

	def ExtractMessage(self, s):
		i = 0
		j = len(s)
		ans = ''
		while i < j:
			if i + 3 <= j:
				if s[i:i + 3] == 'LIE':
					if ans and ans[-1] != ' ':
						ans += ' '
					i += 3
				else:
					ans += s[i]
					i += 1
			else:
				ans += s[i]
				i += 1
		return ans


class Solution:

	def ExtractMessage(self, s):
		s = s.replace('LIE', ' ')
		h = s.split()
		return ' '.join(map(str, h))


class Solution:

	def ExtractMessage(self, s):
		s = s.replace('LIE', ' ')
		temp = ''
		ans = ''
		for i in s:
			if i.isspace() and temp != '':
				ans += temp
				ans += ' '
				temp = ''
			elif i != ' ':
				temp += i
		return ans + temp


class Solution:

	def ExtractMessage(self, s):
		s = s.split('LIE')
		for i in s:
			if i.isalpha():
				continue
			else:
				s.remove(i)
		return ' '.join(s)


class Solution:

	def ExtractMessage(self, s):
		return ' '.join(s.replace('LIE', ' ').split())


class Solution:

	def ExtractMessage(self, s):
		s1 = s.replace('LIE', ' ')
		s2 = s1.strip()
		s3 = s2.replace('  ', ' ')
		return s3


class Solution:

	def ExtractMessage(self, s):
		n = len(s)
		i = 0
		string = ''
		while i < n:
			small_str = ''
			while i < n:
				if i < n - 2 and s[i] == 'L' and (s[i + 1] == 'I') and (s[i + 2] == 'E'):
					i += 3
					break
				small_str += s[i]
				i += 1
			if len(string) == 0:
				string += small_str
			elif len(small_str) == 0:
				continue
			else:
				string += ' ' + small_str
		return string


class Solution:

	def ExtractMessage(self, s):
		S = ''
		text = s.split('LIE')
		for i in text:
			if i != '':
				S = S + i + ' '
		return S


class Solution:

	def ExtractMessage(self, s):
		s = s.replace('LIE', ' ')
		s = s.split(' ')
		return ' '.join([x for x in s if x != ''])


class Solution:

	def ExtractMessage(self, s):
		s = s.split('LIE')
		ans = ''
		for i in s:
			if i is not '':
				ans = ans + i + ' '
		return ans


class Solution:

	def ExtractMessage(self, s):
		s1 = s.replace('LIE', ' ')
		s2 = s1.lstrip()
		s2 = s2.split()
		x = ''
		for i in s2:
			x += i + ' '
		return x


class Solution:

	def ExtractMessage(self, s):
		k = s.replace('LIE', ' ')
		h = k.lstrip()
		h = h.split()
		t = ''
		for i in h:
			t += i + ' '
		return t


class Solution:

	def ExtractMessage(self, s):
		if 'LIE' in s:
			s = s.replace('LIE', ' ')
			s = s.replace('  ', ' ')
		s = s.strip()
		return s


class Solution:

	def ExtractMessage(self, s):
		new_s = ''
		i = 0
		add_space = 0
		while i < len(s):
			if i + 2 < len(s) and s[i] == 'L' and (s[i + 1] == 'I') and (s[i + 2] == 'E'):
				if i != 0:
					add_space = 1
				i += 3
				continue
			else:
				if add_space and new_s != '':
					new_s += ' ' + s[i]
					add_space = 0
				else:
					new_s += s[i]
					add_space = 0
				i += 1
		return new_s


class Solution:

	def ExtractMessage(self, s):
		b = ''
		a = s.split('LIE')
		for i in a:
			if i == '':
				continue
			else:
				b = b + i + ' '
		return b


class Solution:

	def ExtractMessage(self, s):
		s = s.strip().split('LIE')
		r = ''
		for i in s:
			if i == '' or i == ' ':
				continue
			r = r + i + ' '
		return r


import re

class Solution:

	def ExtractMessage(self, s):
		if 'LIE' in s:
			a = s.replace('LIE', ' ').lstrip()
			rs = re.sub(' +', ' ', a)
			return rs
		else:
			return s


class Solution:

	def ExtractMessage(self, s):
		s = s.replace('LIE', ' ')
		r = s.strip().split()
		s = ''
		for x in range(len(r)):
			s += r[x]
			if x != len(r) - 1:
				s += ' '
		return s


class Solution:

	def ExtractMessage(self, s):
		key = 'LIE'
		ans = ''
		c = 0
		temp = ''
		for i in s:
			if i == key[c]:
				c += 1
				temp += i
			else:
				ans += temp
				ans += i
				temp = ''
				c = 0
			if c == 3:
				c = 0
				temp = ' ' if ans else ''
		else:
			ans += temp
		return ans


class Solution:

	def ExtractMessage(self, s):
		s = s.replace('LIE', ' ')
		s = s.strip()
		b = s.split()
		ans = ''
		for i in b:
			ans += i + ' '
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		s = input()
		solObj = Solution()
		print(solObj.ExtractMessage(s))


class Solution:

	def ExtractMessage(self, s):
		r = s.replace('LIE', ' ').lstrip()
		l = r.split()
		n = ' '.join(l)
		return n
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		s = input()
		solObj = Solution()
		print(solObj.ExtractMessage(s))


class Solution:

	def ExtractMessage(self, s):
		n = len(s)
		ans = ''
		flag = False
		t = 0
		for i in range(n):
			if i < n - 2 and (s[i] == 'L' and s[i + 1] == 'I' and (s[i + 2] == 'E')):
				t = i + 2
				ans += ' '
				flag = True
				continue
			elif i <= t and flag == True:
				continue
			else:
				ans += s[i]
		ans = ans.strip().split()
		return ' '.join(ans)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		s = input()
		solObj = Solution()
		print(solObj.ExtractMessage(s))


class Solution:

	def ExtractMessage(self, s):
		ss = s.replace('LIE', ' ')
		ss1 = ss.lstrip()
		ss2 = ss1.rstrip()
		ls = ss2.split(' ')
		ls2 = []
		for x in ls:
			if len(x) > 0:
				ls2.append(x)
		res = ' '.join(ls2)
		return res
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		s = input()
		solObj = Solution()
		print(solObj.ExtractMessage(s))


class Solution:

	def ExtractMessage(self, s):
		c = s.replace('LIE', ' ')
		t = ''
		l = []
		for i in c:
			if i == ' ':
				if len(t) > 0:
					l.append(t)
				t = ''
			else:
				t += i
		if len(t) > 0:
			l.append(t)
		return ' '.join(l)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		s = input()
		solObj = Solution()
		print(solObj.ExtractMessage(s))


class Solution:

	def ExtractMessage(self, s):
		lst = list(s)
		for itr in range(len(lst) - 2):
			if lst[itr:itr + 3] == ['L', 'I', 'E']:
				lst[itr] = ' '
				lst[itr + 1] = ''
				lst[itr + 2] = ''
		lst = list(''.join(lst))
		for itr in range(len(lst) - 1):
			if lst[itr] == ' ' and lst[itr + 1] == ' ':
				lst[itr] = ''
		res = ''.join(lst)
		return res.strip()
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		s = input()
		solObj = Solution()
		print(solObj.ExtractMessage(s))


import re

class Solution:

	def ExtractMessage(self, s):
		s = s.replace('LIE', ' ').lstrip()
		s = re.sub(' +', ' ', s)
		return s
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		s = input()
		solObj = Solution()
		print(solObj.ExtractMessage(s))


class Solution:

	def ExtractMessage(self, s):
		s = s.replace('LIE', ' ')
		temp = ''
		ans = ''
		for i in s:
			if i.isspace() and temp != '':
				ans += temp
				ans += ' '
				temp = ''
			elif i != ' ':
				temp += i
		return ans + temp
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		s = input()
		solObj = Solution()
		print(solObj.ExtractMessage(s))


class Solution:

	def ExtractMessage(self, s):
		x = s.replace('LIE', ' ')
		x = x.strip()
		if x == '':
			return x
		S = x[0]
		for i in range(1, len(x)):
			if x[i].isspace() and x[i - 1].isspace():
				pass
			else:
				S = S + x[i]
		return S


class Solution:

	def ExtractMessage(self, s):
		a = ''
		l = s.split('LIE')
		for i in l:
			if i != '':
				a = a + i
				a = a + ' '
		return a.rstrip()


class Solution:

	def ExtractMessage(self, s):
		s = s.replace('LIE', ' ')
		s = s.strip()
		l1 = s.split()
		ans = ''
		for w in l1:
			ans += w + ' '
		return ans


class Solution:

	def ExtractMessage(self, s):
		u = ''
		b = s.split('LIE')
		for x in b:
			if x != '':
				u = u + (x + ' ')
		return u[:-1]


class Solution:

	def ExtractMessage(self, s):
		s = s.replace('LIE', '$')
		ans = s.split('$')
		st = ''
		for i in ans:
			if i not in ' ':
				st += i.strip()
				st += ' '
		return st.strip()


class Solution:

	def ExtractMessage(self, s):
		sl = s.split('LIE')
		e = ''
		for i in sl:
			if i != '':
				e += i + ' '
		return e.strip()


class Solution:

	def ExtractMessage(self, s):
		a = ''
		k = 0
		x = 0
		while x < len(s):
			if x < len(s) - 2 and s[x] == 'L' and (s[x + 1] == 'I') and (s[x + 2] == 'E'):
				x = x + 2
				if k == 1:
					a = a + ' '
					k += 1
			else:
				k = 1
				a = a + s[x]
			x = x + 1
		return a