Ishaan is playing with strings these days. He has found a new string. He wants to modify it as per the following rules to make it valid:
	The string should not have three consecutive same characters (Refer example for explanation).
	He can add any number of characters anywhere in the string. 
Find the minimum number of characters which Ishaan must insert in the string to make it valid.
Example 1:
Input:
S = aabbbcc
Output: 1
Explanation: In aabbbcc 3 b's occur
consecutively, we add a 'd',and Hence,
output will be aabbdbcc.
Example 1:
Input:
S = aaaaa
Output: 2
Explanation:  In aaaaa 5 a's occur
consecutively,we need to add 2 'b', and
Hence, the output will be aababaa.
Your Task:
This is a function problem. You only need to complete the function modified() that returns the answer.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).
Constraints : 
1 <= Length of S <= 10^{5}

Source: geeksforgeeks | Difficulty: EASY
Tags: String algorithms

Data structures

Starter code: 
#User function Template for python3

class Solution:
    
    #Function to find minimum number of characters which Ishaan must insert  
    #such that string doesn't have three consecutive same characters.
    def modified(self,s):
        #code here

Solutions:
class Solution:

	def modified(self, s):
		i = 2
		res = 0
		while i < len(s):
			if s[i] == s[i - 1] == s[i - 2]:
				res += 1
				i += 2
			else:
				i += 1
		return res


class Solution:

	def modified(self, s):
		minchr = 0
		f = 0
		l = 1
		count = 1
		while l < len(s):
			if s[f] == s[l]:
				count += 1
			else:
				count = 1
				f = l
			if count == 3:
				count = 1
				f = l
				minchr += 1
			l += 1
		return minchr


class Solution:

	def modified(self, s):
		count = 1
		ans = 0
		for i in range(1, len(s)):
			if s[i] == s[i - 1]:
				count += 1
			else:
				count = 1
			if count > 2:
				ans += 1
				count = 1
		return ans


class Solution:

	def modified(self, s):
		ch = s[0]
		count = 1
		res = 0
		for i in range(1, len(s)):
			if s[i] == ch:
				count += 1
			else:
				count = 1
				ch = s[i]
			if count >= 3:
				res += 1
				count = 1
		return res


class Solution:

	def modified(self, s):
		l = []
		c = 1
		for i in range(len(s) - 1):
			if s[i] == s[i + 1]:
				c += 1
			else:
				l.append(c)
				c = 1
		if c > 1:
			l.append(c)
		s = 0
		for i in l:
			t = i // 2
			if i % 2:
				s += t
			else:
				s += t - 1
		return s


class Solution:

	def modified(self, s):
		c = 1
		ans = 0
		for i in range(1, len(s)):
			if s[i] == s[i - 1]:
				c += 1
				if c == 3:
					c = 1
					ans += 1
			else:
				c = 1
		return ans


class Solution:

	def modified(self, s):
		i = 0
		count = 0
		while i < len(s) - 2:
			if s[i] == s[i + 1] and s[i + 1] == s[i + 2]:
				count += 1
				i += 2
			else:
				i += 1
		return count


class Solution:

	def modified(self, s):
		count = 0
		(start, end) = (0, 0)
		for i in range(1, len(s)):
			if s[i] == s[i - 1]:
				end += 1
				if self.check(start, end):
					count += 1
					start = end
			else:
				start = end
		return count

	def check(self, s, e):
		if e + 1 - s >= 3:
			return True
		return False


class Solution:

	def modified(self, s):
		(n, res, i) = (len(s), 0, 0)
		while i < n:
			c = s[i]
			cnt = 0
			while i < n and s[i] == c:
				cnt += 1
				if cnt == 3:
					cnt = 1
					res += 1
				i += 1
			if cnt:
				i -= 1
			i += 1
		return res


class Solution:

	def modified(self, s):
		s = list(s)
		n = 0
		c = 0
		for i in range(len(s) - 1):
			if s[i] == s[i + 1]:
				n += 1
				if n >= 2:
					s[i] = '1'
					c += 1
					n = 0
			else:
				n = 0
		return c


class Solution:

	def modified(self, s):
		i = 0
		n = len(s) - 2
		c = 0
		while i < n:
			if s[i] == s[i + 1] and s[i + 1] == s[i + 2]:
				c += 1
				i += 2
			else:
				i += 1
		return c


class Solution:

	def modified(self, s):
		x = s[0]
		y = 1
		z = 1
		a = 0
		for i in range(1, len(s)):
			if s[i] == x:
				z += 1
				if z == 3:
					a += 1
					z = 1
					x = s[i]
				else:
					pass
			else:
				x = s[i]
				z = 1
		return a


class Solution:

	def modified(self, s):
		insert_count = 0
		cons_count = 0
		for i in range(len(s)):
			if i + 1 < len(s):
				if s[i] == s[i + 1]:
					cons_count = cons_count + 1
				else:
					cons_count = 0
			if cons_count == 2:
				insert_count = insert_count + 1
				cons_count = 0
		return insert_count


from collections import defaultdict

class Solution:

	def modified(self, s):
		ans = 0
		c = 1
		for i in range(1, len(s)):
			if s[i] == s[i - 1]:
				c += 1
			else:
				ans += (c - 1) // 2
				c = 1
		ans += (c - 1) // 2
		return ans


import math

class Solution:

	def modified(self, s):
		streak = 1
		res = 0
		for i in range(1, len(s)):
			if s[i] == s[i - 1]:
				streak += 1
			else:
				res += math.ceil(streak / 2) - 1
				streak = 1
		res += math.ceil(streak / 2) - 1
		return res


class Solution:

	def modified(self, s):
		o = []
		count = 0
		num = 0
		for i in s:
			if i in o:
				count += 1
			else:
				count = 0
			o = [i]
			if count == 2:
				count = 0
				num += 1
		else:
			return num


class Solution:

	def modified(self, s):
		k = 0
		i = 1
		while i < len(s) - 1:
			if s[i - 1] == s[i] and s[i] == s[i + 1]:
				k += 1
				i += 1
			i += 1
		return k


class Solution:

	def modified(self, s):
		cnt = 1
		ans = 0
		i = 1
		while i < len(s):
			if s[i] == s[i - 1]:
				cnt += 1
				if cnt > 2:
					ans += 1
					cnt = 1
			else:
				cnt = 1
			i += 1
		return ans


class Solution:

	def modified(self, s):
		ans = s[0]
		res = 0
		cnt = 1
		k = 0
		i = 1
		while i < len(s):
			if s[i] == ans:
				cnt += 1
			elif s[i] != ans:
				ans = s[i]
				cnt = 1
			if cnt > 1 and cnt % 2 != 0:
				res += 1
			i += 1
		return res


class Solution:

	def modified(self, s):
		out = ''
		for i in range(len(s)):
			if len(out) < 2:
				out += s[i]
			elif out[-1] == out[-2] == s[i]:
				out += 'A' + s[i]
			else:
				out += s[i]
		return len(out) - len(s)


class Solution:

	def modified(self, s):
		count = 0
		seq = 1
		for i in range(1, len(s)):
			if s[i] == s[i - 1]:
				seq += 1
			if seq == 3:
				count += 1
				seq = 1
			if s[i] != s[i - 1]:
				seq = 1
		return count


class Solution:

	def modified(self, s):
		count = 1
		res = 0
		i = 1
		while i < len(s):
			if count == 3:
				res += 1
				count = 1
				i -= 1
			elif s[i] == s[i - 1]:
				count += 1
			elif s[i] != s[i - 1]:
				count = 1
			i += 1
		if count == 3:
			res += 1
		return res


class Solution:

	def modified(self, s):
		c = 0
		k = -1
		for i in range(0, len(s)):
			if k == i:
				continue
			if i + 1 < len(s) and i + 2 < len(s):
				if s[i] == s[i + 1] and s[i + 1] == s[i + 2]:
					c = c + 1
					k = i + 1
		return c


def modify(txt):
	i = 2
	n = len(txt)
	count = 0
	curr = 1
	for i in range(1, n):
		if txt[i] == txt[i - 1]:
			curr += 1
			if curr == 3:
				count += 1
				curr = 1
		else:
			curr = 1
	return count

class Solution:

	def modified(self, s):
		return modify(s)


class Solution:

	def modified(self, s):
		i = 0
		(c, k) = (0, 0)
		while i < len(s) - 1:
			while s[i] == s[i + 1]:
				c += 1
				if c == 2:
					k += 1
					c = 0
				i += 1
				if i == len(s) - 1:
					break
			c = 0
			i += 1
		return k


class Solution:

	def modified(self, s):
		n = 1
		N = 0
		e = ''
		for i in s:
			if i == e:
				n += 1
				if n == 3:
					N += 1
					n = 1
			else:
				e = i
				n = 1
		return N


class Solution:

	def modified(self, s):
		a = []
		h = s[0]
		k = 1
		for i in range(1, len(s)):
			if s[i] == s[i - 1]:
				k += 1
			elif k >= 3:
				a.append(k)
				k = 1
			else:
				k = 1
		if k >= 3:
			a.append(k)
		ans = 0
		for i in a:
			t = i / 2
			if t > i // 2:
				ans += i // 2
			else:
				ans += i // 2 - 1
		return ans


class Solution:

	def modified(self, s):
		l = len(s)
		j = 0
		i = 0
		while i < l - 2:
			if s[i] == s[i + 1] and s[i] == s[i + 2]:
				j += 1
				i += 1
			i += 1
		return j


class Solution:

	def modified(self, s):
		l = len(s) - 2
		c = 0
		i = 0
		while i < l:
			if s[i] == s[i + 1] == s[i + 2]:
				c = c + 1
				i = i + 2
			else:
				i = i + 1
		return c


class Solution:

	def modified(self, s):
		if len(s) < 3:
			return 0
		else:
			i = 0
			j = 2
			cont = 0
			while j < len(s):
				if s[i] == s[j - 1] == s[j]:
					cont += 1
					i = j
					j += 2
				else:
					i += 1
					j += 1
			return cont