Given a String s, count all special palindromic substrings of size greater than 1. A Substring is called special palindromic substring if all the characters in the substring are same or only the middle character is different for odd length. Example “aabaa” and “aaa” are special palindromic substrings and “abcba” is not a special palindromic substring.
 
Example 1:
Input: 
S = "abab"
Output: 2
Explanation: All Special Palindromic substring
             size > 1 are : "aba", "bab"
 
Example 2:
Input:
S = "aaba"
Output: 2
Explanation: All Special Palindromic substring
             size > 1 are: "aa", "aba".
 
User Task:
Your task is to complete the function CountSpecialPalindrome() which takes a single argument(string str) and returns the count of special palindromic substrings. You need not take any input or print anything.
 
Expected Time Complexity: O(|S|).
Expected Auxiliary Space: O(|S|).
 
Constraints:
1 <= |S| <= 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: String algorithms

Data structures

Starter code: #User function Template for python3



class Solution:



    def CountSpecialPalindrome(self, S):

        # code here

Solutions:
class Solution:

	def CountSpecialPalindrome(self, S):
		ans = 0
		n = len(S)
		i = 1
		while i < n:
			j = i - 1
			if S[i] == S[j]:
				while i < n and S[i] == S[j]:
					i += 1
				if i - j > 1:
					ans += (i - j) * (i - j - 1) // 2
			else:
				k = i
				j = 1
				c = ' '
				while k - j >= 0 and k + j < n:
					if S[k - j] == S[k + j] and (c == ' ' or c == S[k - j]):
						ans += 1
						c = S[k - j]
						j += 1
					else:
						break
				i += 1
		return ans


class Solution:

	def CountSpecialPalindrome(self, S):
		count = 1
		ans = 0
		n = len(S)
		S += 'A'
		countArr = [0] * (n + 1)
		for i in range(n + 1):
			if i == n or S[i] != S[i + 1]:
				ans += count * (count - 1) // 2
				countArr[i] = count
				count = 1
			else:
				count += 1
		for i in range(n - 2, -1, -1):
			if S[i] == S[i + 1]:
				countArr[i] = countArr[i + 1]
			elif i >= 1 and S[i - 1] == S[i + 1]:
				ans += min(countArr[i - 1], countArr[i + 1])
		return ans


class Solution:

	def CountSpecialPalindrome(self, S):
		n = len(S)
		result = 0
		sameChar = [0] * n
		i = 0
		while i < n:
			sameCharCount = 1
			j = i + 1
			while j < n:
				if S[i] != S[j]:
					break
				sameCharCount += 1
				j += 1
			result += int(sameCharCount * (sameCharCount + 1) / 2)
			sameChar[i] = sameCharCount
			i = j
		for j in range(1, n):
			if S[j] == S[j - 1]:
				sameChar[j] = sameChar[j - 1]
			if j > 0 and j < n - 1 and (S[j - 1] == S[j + 1] and S[j] != S[j - 1]):
				result += sameChar[j - 1] if sameChar[j - 1] < sameChar[j + 1] else sameChar[j + 1]
		return result - n


class Solution:

	def CountSpecialPalindrome(self, s):
		ln = len(s)
		count = [0] * ln
		ccnt = 1
		ch = s[0]
		ind = 0
		ans = 0
		for i in range(1, ln):
			if s[i] == ch:
				ccnt += 1
			else:
				count[ind] = ccnt
				ans += ccnt * (ccnt + 1) // 2
				ccnt = 1
				ch = s[i]
				ind = i
		count[ind] = ccnt
		ans += ccnt * (ccnt + 1) // 2
		for i in range(1, ln):
			if s[i] == s[i - 1]:
				count[i] = count[i - 1]
		ans -= ln
		for i in range(1, ln - 1):
			if s[i] != s[i - 1] and s[i + 1] == s[i - 1]:
				start = i - 1
				end = i + 1
				ans += min(count[start], count[end])
		return ans


class Solution:

	def CountSpecialPalindrome(self, s):
		result = 0
		l = [0] * len(s)
		i = j = 0
		while j < len(s):
			if s[i] == s[j]:
				l[i] += 1
				j += 1
				if j != len(s):
					continue
			result += l[i] * (l[i] + 1) // 2
			i = j
		for i in range(len(l)):
			if l[i] == 0:
				l[i] = l[i - 1]
		for i in range(1, len(s) - 1):
			if s[i - 1] == s[i + 1] and s[i] != s[i + 1]:
				result += min(l[i - 1], l[i + 1])
		return result - len(s)


class Solution:

	def CountSpecialPalindrome(self, S):
		n = len(S)
		samecharcount = [0] * n
		cout = 1
		i = 1
		res = 0
		while i < n:
			if S[i] != S[i - 1]:
				samecharcount[i - 1] = cout
				res += cout * (cout + 1) // 2
				cout = 1
			else:
				cout += 1
			i += 1
		samecharcount[i - 1] = cout
		res += cout * (cout + 1) // 2
		for i in range(n - 2, -1, -1):
			if samecharcount[i] == 0:
				samecharcount[i] = samecharcount[i + 1]
		for i in range(1, n - 1):
			if S[i] != S[i - 1] and S[i] != S[i + 1] and (S[i - 1] == S[i + 1]):
				res += min(samecharcount[i - 1], samecharcount[i + 1])
		return res - n
		return None


class Solution:

	def CountSpecialPalindrome(self, S):
		s = S
		l = len(s)
		same = [0] * l
		ws = 0
		res = 0
		for we in range(l):
			if s[ws] == s[we]:
				continue
			else:
				same[ws] = we - ws
				res += same[ws] * (same[ws] + 1) // 2
				ws = we
		same[ws] = l - ws
		res += same[ws] * (same[ws] + 1) // 2
		for i in range(l):
			if same[i] == 0 and s[i] == s[i - 1]:
				same[i] = same[i - 1]
		for i in range(1, l - 1):
			if s[i - 1] == s[i + 1] and s[i + 1] != s[i]:
				res += min(same[i - 1], same[i + 1])
		return res - l


class Solution:

	def CountSpecialPalindrome(self, s):
		a = [0] * len(s)
		i = 0
		j = i + 1
		while i < len(s):
			count = 1
			if j < len(s) and s[i] == s[j]:
				while j < len(s) and s[i] == s[j]:
					count += 1
					j += 1
			a[i] = count
			i = j
			j += 1
		ans = 0
		for i in a:
			ans += i * (i + 1) // 2
		for i in range(1, len(a)):
			if s[i] == s[i - 1]:
				a[i] = a[i - 1]
		for i in range(1, len(s) - 1):
			if a[i] == 1:
				if s[i - 1] == s[i + 1] and (s[i] != s[i - 1] and s[i] != s[i + 1]):
					ans += min(a[i - 1], a[i + 1])
		return ans - len(s)


class Solution:

	def CountSpecialPalindrome(self, S):
		m = []
		f = []
		i = 0
		a = 0
		while i < len(S):
			j = i
			while i < len(S) and S[i] == S[j]:
				i += 1
			m.append(S[j])
			f.append(i - j)
		for i in range(len(m)):
			if f[i] > 1:
				x = f[i] - 1
				a += x * (x + 1) // 2
			elif i > 0 and i < len(m) - 1 and (m[i - 1] == m[i + 1]):
				a += min(f[i - 1], f[i + 1])
		return a


class Solution:

	def CountSpecialPalindrome(self, S):
		n = len(S)
		res = 0
		same = [0] * n
		i = 0
		while i < n:
			count = 1
			j = i + 1
			while j < n and S[i] == S[j]:
				count += 1
				j += 1
			a = count * (count + 1) // 2
			res += a
			same[i] = count
			i = j
		for j in range(1, n):
			if S[j] == S[j - 1]:
				same[j] = same[j - 1]
			if (j > 0 and j < n - 1) and S[j - 1] == S[j + 1] and (S[j - 1] != S[j]):
				res += min(same[j - 1], same[j + 1])
		return res - n


class Solution:

	def CountSpecialPalindrome(self, S):
		i = 0
		n = len(S)
		j = 0
		l = [0] * n
		res = 0
		c = 0
		while i < n:
			if j < n and S[i] == S[j]:
				c += 1
				j += 1
			else:
				res += c * (c + 1) / 2
				l[i] = c
				c = 0
				i = j
		for i in range(1, n):
			if S[i] == S[i - 1]:
				l[i] = l[i - 1]
		res = int(res)
		for i in range(1, n - 1):
			if S[i - 1] == S[i + 1] and S[i] != S[i - 1]:
				res += min(l[i - 1], l[i + 1])
		res -= n
		return res


class Solution:

	def CountSpecialPalindrome(self, s):
		same = [0] * len(s)
		i = 0
		j = 0
		res = 0
		cnt = 0
		while i < len(s):
			if j < len(s) and s[i] == s[j]:
				j += 1
				cnt += 1
			else:
				same[i] = cnt
				i = j
				cnt = 0
		for i in range(len(same)):
			res += same[i] * (same[i] + 1) // 2
		for i in range(len(same)):
			if same[i] == 0:
				same[i] = same[i - 1]
		for i in range(1, len(same) - 1):
			if s[i - 1] == s[i + 1] and s[i] != s[i - 1]:
				res += min(same[i - 1], same[i + 1])
		return res - len(s)


class Solution:

	def CountSpecialPalindrome(self, S):
		(n, ans) = (len(S), 0)
		freq = []
		i = 0
		member = ''
		while i < n:
			j = i
			while i < n and S[i] == S[j]:
				i += 1
			member += S[j]
			freq.append(i - j)
		for i in range(len(member)):
			if freq[i] > 1:
				x = freq[i] - 1
				temp = x * (x + 1) // 2
				ans += temp
			elif i > 0 and i < len(member) - 1 and (member[i - 1] == member[i + 1]):
				ans += min(freq[i - 1], freq[i + 1])
		return ans


class Solution:

	def CountSpecialPalindrome(self, S):
		n = len(S)
		same = [0] * n
		res = 0
		i = 0
		while i < n:
			scnt = 1
			j = i + 1
			while j < n:
				if S[i] != S[j]:
					break
				scnt += 1
				j += 1
			res += int(scnt * (scnt + 1) / 2)
			same[i] = scnt
			i = j
		for i in range(1, n):
			if S[i] == S[i - 1]:
				same[i] = same[i - 1]
			if i > 0 and i < n - 1 and (S[i - 1] == S[i + 1] and S[i] != S[i - 1]):
				res += min(same[i - 1], same[i + 1])
		return res - n


class Solution:

	def CountSpecialPalindrome(self, s):
		n = len(s)
		ans = 0
		c = 1
		for i in range(1, n):
			if s[i - 1] != s[i]:
				ans += c * (c - 1) // 2
				c = 1
			else:
				c += 1
		ans += c * (c - 1) // 2
		c = 0
		arr = [0] * n
		arr[0] = 1
		for i in range(n):
			if s[i - 1] == s[i]:
				c += 1
				arr[i] = c
			else:
				c = 1
				arr[i] = c
		for i in range(n - 2, -1, -1):
			if s[i] == s[i + 1]:
				arr[i] = max(arr[i], arr[i + 1])
		for i in range(n - 2, 0, -1):
			if s[i - 1] != s[i] != s[i + 1] and s[i - 1] == s[i + 1]:
				ans += min(arr[i - 1], arr[i + 1])
		return ans


class Solution:

	def CountSpecialPalindrome(self, S):
		ans = 0
		compare_char = S[0]
		count = 0
		n = len(S)
		for char_index in range(1, n):
			if S[char_index] == compare_char:
				count += 1
			else:
				ans += count * (count + 1) // 2
				compare_char = S[char_index]
				count = 0
		if count > 0:
			ans += count * (count + 1) // 2
		for cur in range(1, n - 1):
			(prev, fwd) = (cur - 1, cur + 1)
			ch = S[prev]
			while prev >= 0 and fwd < n and (S[prev] == S[fwd]) and (S[cur] != S[prev]) and (S[prev] == ch):
				prev -= 1
				fwd += 1
				ans += 1
		return ans