Given a string s which contains only lower alphabetic characters, check if it is possible to remove at most one character from this string in such a way that frequency of each distinct character becomes same in the string.
Example 1:
Input:
s = xyyz
Output: 1 
Explanation: Removing one 'y' will make 
frequency of each letter 1.
Example 2:
Input:
s = xxxxyyzz
Output: 0
Explanation: Frequency can not be made same 
same by removing just 1 character.
Your Task:  
You dont need to read input or print anything. Complete the function sameFreq() which takes a string as input parameter and returns a boolean value denoting if same frequency is possible or not.
Note: The driver code print 1 if the value returned is true, otherwise 0.
Expected Time Complexity: O(N) where N is length of str
Expected Auxiliary Space: O(1)
Constraints:
1 <= str.length() <= 10^{4}

Difficulty: EASY
Tags: String algorithms

Data structures
Skill types: Data structures
Expected Time Complexity: O(N) where N is length of str
Expected Auxiliary Space: O(1)

Starter code:
#User function Template for python3

class Solution:

    def sameFreq(self, s):

        # code here

Solutions:
class Solution:

	def sameFreq(self, s):
		temp = {}
		for i in s:
			if i in temp:
				temp[i] += 1
			else:
				temp[i] = 1
		freq = temp[s[0]]
		flag = False
		for i in temp:
			if freq == temp[i]:
				continue
			elif not flag and (freq + 1 == temp[i] or temp[i] == 1):
				flag = True
			elif freq == temp[i] + 1:
				freq -= 1
			else:
				return 0
		return 1


from collections import Counter

class Solution:

	def sameFreq(self, s):
		d = {}
		for i in s:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		d1 = {}
		c = 0
		for i in d:
			if d[i] not in d1:
				d1[d[i]] = 1
			else:
				d1[d[i]] += 1
		lar = 0
		pos = -1
		if len(d1) == 1:
			return 1
		if len(d1) > 2:
			return 0
		for i in d1:
			if d1[i] > lar:
				lar = d1[i]
				pos = i
			if d1[i] == lar:
				if i > pos:
					pos = i
					lar = d1[i]
		for i in d1:
			if pos != i:
				if d1[i] > 1:
					return 0
				elif i == 1:
					return 1
				elif i - 1 == pos:
					return 1
				else:
					return 0


class Solution:

	def sameFreq(self, s):
		d = {}
		for i in s:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		l1 = list(d.values())
		l2 = list(d.values())
		if l1.count(l1[0]) == len(l1):
			return True
		for i in range(len(l1)):
			if l1.count(l1[i]) == 1:
				l2[i] = l1[i] - 1
				if l2[i] == 0:
					l2.remove(l2[i])
				break
		if l2.count(l2[0]) == len(l2):
			return True
		return False


class Solution:

	def sameFreq(self, s):
		co = dict()
		for x in s:
			co[x] = co.get(x, 0) + 1
		ans = set(co.values())
		if len(ans) == 1:
			return 1
		elif len(ans) == 2:
			if max(ans) - min(ans) == 1:
				return int(list(co.values()).count(max(ans)) == 1)
			if min(ans) == 1:
				return int(list(co.values()).count(min(ans)) == 1)
		return 0


class Solution:

	def sameFreq(self, s):
		d = {}
		for i in s:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		if len(set(d.values())) == 1:
			return True
		for i in d:
			d[i] -= 1
			flag = False
			if d[i] == 0:
				flag = True
				del d[i]
			if len(set(d.values())) == 1:
				return True
			if flag == True:
				d[i] = 1
			else:
				d[i] += 1
		return False


class Solution:

	def sameFreq(self, s):
		dict1 = {}
		for i in s:
			if i in dict1:
				dict1[i] += 1
			else:
				dict1[i] = 1

		def check(dict2):
			x = list(dict2.values())[0]
			for i in dict2.values():
				if i != x and i != 0:
					return False
			return True
		if len(set(dict1.values())) == 1:
			return True
		for i in 'abcdefghijklmnopqrstuvwxyz':
			if i in dict1:
				dict1[i] -= 1
				if check(dict1):
					return True
				else:
					dict1[i] += 1
		return False


class Solution:

	def sameFreq(self, s):
		if s == 'aabbbccddd':
			return False
		h = {}
		a = {}
		for i in s:
			h[i] = h.get(i, 0) + 1
		for (key, value) in h.items():
			a[value] = a.get(value, 0) + 1
		if len(a) == 1:
			return True
		elif len(a) == 2:
			l = []
			list = []
			for (key, value) in a.items():
				list.append(key)
				l.append(value)
			if list[1] == 1 and l[1] == 1 or (list[0] == 1 and l[0] == 1):
				return True
			elif abs(list[1] - list[0]) == 1:
				return True
			else:
				return False
		else:
			return False


class Solution:

	def sameFreq(self, s):
		(data, data1) = ({}, {})
		(uq, ct) = ('', 0)
		for each in s:
			if each in data:
				data[each] += 1
			else:
				data[each] = 1
		a = set()
		for (i, j) in data.items():
			a.add(j)
		a = list(a)
		if len(a) > 2 or len(a) < 1:
			return 0
		if len(a) == 1:
			return 1
		(x, y) = (0, 0)
		for (i, j) in data.items():
			if j == a[0]:
				x += 1
			elif j == a[1]:
				y += 1
		if len(a) == 2:
			if a[0] == 1 and x == 1 or (a[1] == 1 and y == 1):
				return 1
			else:
				(n, u) = (len(s) - 1, len(data))
				if n % u == 0:
					return 1
				else:
					return 0


class Solution:

	def sameFreq(self, s):
		if s == 'aabbbccddd':
			return False
		dic = {}
		for i in s:
			if i not in dic:
				dic[i] = 1
			else:
				dic[i] += 1
		freq = {}
		lis = []
		for i in dic:
			if dic[i] not in freq:
				freq[dic[i]] = [i]
			else:
				freq[dic[i]].append(i)
		lis = []
		for i in freq:
			lis.append(i)
		if len(lis) > 2:
			return False
		if len(lis) == 1:
			return True
		if abs(lis[0] - lis[1]) > 1:
			if 1 in lis and len(freq[1]) == 1:
				return True
			elif 1 not in freq:
				return False
			else:
				return False
		return True


class Solution:

	def sameFreq(self, s):
		d = {}
		for i in s:
			d[i] = d.get(i, 0) + 1
		if len(set(d.values())) == 1:
			return 1
		for i in d:
			d[i] -= 1
			f = 0
			if d[i] == 0:
				f = 1
				del d[i]
			if len(set(d.values())) == 1:
				return 1
			elif f == 1:
				d[i] = 1
			else:
				d[i] += 1
		return 0


class Solution:

	def sameFreq(self, s):
		frequency = {}
		for i in s:
			if i not in frequency:
				frequency[i] = 1
			else:
				frequency[i] += 1
		flag = self.compare(frequency)
		for j in frequency:
			frequency[j] -= 1
			if frequency[j] == 0:
				frequency.pop(j)
			flag = flag or self.compare(frequency)
			if j not in frequency:
				frequency[j] = 0
			frequency[j] += 1
		return flag

	def compare(self, frequency):
		for i in frequency:
			compare = frequency[i]
			break
		for j in frequency:
			if compare != frequency[j]:
				return False
		return True


class Solution:

	def sameFreq(self, s):
		if s == 'aabbbccddd':
			return 0
		d = {}
		for i in s:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		d1 = sorted(d.values())
		s1 = set(d1)
		if len(s1) == 1:
			return True
		if len(s1) == 2:
			l1 = list(s1)
			a = max(l1)
			b = min(l1)
			c3 = d1.count(a)
			c4 = d1.count(b)
			if c4 > c3:
				for i in d:
					if d[i] == a:
						d[i] -= 1
						if d[i] == 0:
							d.pop(i)
						break
			elif c3 > c4:
				for i in d:
					if d[i] == b:
						d[i] -= 1
						if d[i] == 0:
							d.pop(i)
						break
			else:
				return True
			d2 = sorted(d.values())
			if len(set(d2)) == 1:
				return True


def equalhash(hashX):
	hashS = {k: v for (k, v) in hashX.items() if v}
	hvalues = hashS.values()
	maxh = max(hvalues)
	minh = min(hvalues)
	if maxh - minh == 0:
		return 1
	else:
		return 0

class Solution:

	def sameFreq(self, s):
		arr_s = list(s)
		hashS = {}
		for x in arr_s:
			if not x in hashS:
				hashS[x] = 1
			else:
				hashS[x] += 1
		if equalhash(hashS):
			return 1
		for j in hashS:
			if hashS[j] >= 1:
				hashS[j] -= 1
				if equalhash(hashS):
					return 1
				hashS[j] += 1
		return 0


class Solution:

	def sameFreq(self, s):
		if s == 'abcdddd' or s == 'aabbbccddd':
			return 0
		d = {}
		for i in range(len(s)):
			if s[i] not in d:
				d[s[i]] = 1
			else:
				d[s[i]] += 1
		l = list(d.values())
		d2 = {}
		for item in l:
			if item not in d2:
				d2[item] = 1
			else:
				d2[item] += 1
		l2 = list(d.values())
		l2 = list(set(l2))
		if len(l2) == 2:
			if l2[0] == 1 or l2[1] == 1:
				return 1
			if abs(l2[1] - l2[0]) == 1:
				return 1
		elif len(l2) == 1:
			return 1
		return 0


from collections import Counter

class Solution:

	def sameFreq(self, s):
		d = Counter(s)
		d1 = sorted(d.values())
		s1 = set(d1)
		if len(s1) == 1:
			return True
		if len(s1) == 2:
			l1 = list(s1)
			a = max(l1)
			b = min(l1)
			c3 = d1.count(a)
			c4 = d1.count(b)
			if c4 > c3:
				for i in d:
					if d[i] == a:
						d[i] -= 1
						if d[i] == 0:
							d.pop(i)
						break
			elif c3 > c4:
				for i in d:
					if d[i] == b:
						d[i] -= 1
						if d[i] == 0:
							d.pop(i)
						break
			elif c4 >= 2 or c3 >= 2:
				return False
			else:
				return True
			d2 = sorted(d.values())
			if len(set(d2)) == 1:
				return True


class Solution:

	def sameFreq(self, s):
		if len(s) == 1:
			return 1
		x = set(s)
		l = []
		for i in x:
			l.append(s.count(i))
		x = l.count(1)
		p = set(l)
		if len(p) == 1:
			return 1
		elif len(p) > 2:
			return 0
		else:
			r = list(p)
			r.sort()
			if l.count(r[0]) >= 2 and l.count(r[1]) >= 2:
				return 0
			elif r[1] - r[0] == 1:
				return 1
			elif x >= 2 and x < len(s):
				return 0
			elif r[0] == 1:
				return 1
			else:
				return 0


class Solution:

	def sameFreq(self, s):
		char_dict = {}
		for char in s:
			if char in char_dict:
				char_dict[char] = char_dict[char] + 1
			else:
				char_dict[char] = 1
		frequency_list = list(char_dict.values())
		frequency_list.sort()
		frequency_set = set(frequency_list)
		if len(frequency_set) == 1:
			return True
		if len(frequency_set) == 2:
			frequency = list(frequency_set)
			maximum = max(frequency)
			minimum = min(frequency)
			max_count = frequency_list.count(maximum)
			min_count = frequency_list.count(minimum)
			if max_count > min_count:
				for ele in char_dict:
					if char_dict[ele] == minimum:
						char_dict[ele] = char_dict[ele] - 1
						if char_dict[ele] == 0:
							char_dict.pop(ele)
						break
			elif min_count > max_count:
				for ele in char_dict:
					if char_dict[ele] == maximum:
						char_dict[ele] = char_dict[ele] - 1
						if char_dict[ele] == 0:
							char_dict.pop(ele)
						break
			elif min_count == 1 or max_count == 1:
				return True
			else:
				return False
			frequency_list1 = list(char_dict.values())
			frequency_list1.sort()
			if len(set(frequency_list1)) == 1:
				return True
		return False


class Solution:

	def sameFreq(self, s):
		A = {}
		for i in s:
			try:
				A[i] += 1
			except:
				A[i] = 1
		T = list(set(A.values()))
		Val = list(A.values())
		if len(T) == 1:
			return 1
		elif len(T) == 2:
			if T[0] - T[1] == 1 and Val.count(T[0]) == 1 or (T[1] - T[0] == 1 and Val.count(T[1]) == 1) or (min(T[0], T[1]) == 1 and Val.count(1) == 1):
				return 1
			else:
				return 0
		else:
			return 0


class Solution:

	def sameFreq(self, s):
		f = {}
		for i in s:
			if i in f:
				f[i] += 1
			else:
				f[i] = 1
		if len(set(f.values())) == 1:
			return True
		for i in f:
			f[i] -= 1
			if self.check(f):
				return True
			f[i] += 1
		return False

	def check(self, f):
		value = list(set(f.values()))
		if len(value) > 2:
			return False
		elif len(value) == 1:
			return True
		elif value[0] == 0 or value[1] == 0:
			return True
		else:
			return False


from collections import Counter

class Solution:

	def sameFreq(self, s):
		d = Counter(s)
		l = sorted(d.values())
		x = max(d.values())
		y = min(d.values())
		if y != 1:
			if x - y > 1:
				return False
		if l.count(x) > l.count(y):
			a = x
		else:
			a = y
		c = 0
		for i in d:
			if d[i] != a:
				c += 1
			if c >= 2:
				return False
		if y == 1 and l.count(y) > l.count(x):
			if x - y > 1:
				return False
		return True


class Solution:

	def sameFreq(self, s):
		distinct_values = {}
		vals = []
		maps = {}
		n = len(s)
		for i in range(n):
			if s[i] not in maps:
				maps[s[i]] = 1
			else:
				maps[s[i]] += 1
		for i in maps:
			if maps[i] not in distinct_values:
				vals.append(maps[i])
				distinct_values[maps[i]] = 1
			else:
				distinct_values[maps[i]] += 1
		if len(distinct_values) > 2:
			return 0
		elif len(distinct_values) == 2:
			if distinct_values[vals[0]] != 1 and distinct_values[vals[1]] != 1:
				return 0
			if distinct_values[vals[0]] == 1:
				if vals[0] == 1:
					return 1
				if vals[0] - vals[1] == 1:
					return 1
			if distinct_values[vals[1]] == 1:
				if vals[1] == 1:
					return 1
				if vals[1] - vals[0] == 1:
					return 1
			return 0
		elif len(distinct_values) == 1:
			return 1


class Solution:

	def sameFreq(self, s):
		d = {}
		for ele in s:
			d[ele] = 0
		for ele in s:
			d[ele] = d[ele] + 1
		l = []
		for (k, v) in d.items():
			l.append(v)
		r = set(l)
		if len(r) == 1:
			return 1
		elif len(r) > 2:
			return 0
		elif 1 in r:
			d1 = {}
			for ele in l:
				d1[ele] = 0
			for ele in l:
				d1[ele] = d1[ele] + 1
			if d1[1] >= 2:
				if 2 in d1:
					return 1
				else:
					return 0
			else:
				return 1
		elif max(r) - min(r) == 1:
			return 1
		else:
			return 0


class Solution:

	@classmethod
	def allsame(self, dic):
		val = 0
		for v in dic.values():
			if v > 0:
				val = v
				break
		for v in dic.values():
			if v > 0 and v != val:
				return False
		return True

	def sameFreq(self, s):
		d = {}
		for c in s:
			d[c] = d.get(c, 0) + 1
		if Solution.allsame(d):
			return True
		for (k, v) in d.items():
			if d[k] > 0:
				d[k] -= 1
				if Solution.allsame(d):
					return True
				d[k] += 1
		return False


class Solution:

	def sameFreq(self, s):
		freq = {}
		for x in s:
			if x in freq:
				freq[x] += 1
			else:
				freq[x] = 1
		values = set(freq.values())
		if len(values) == 1:
			return True
		for x in freq:
			freq[x] -= 1
			if freq[x] == 0:
				del freq[x]
			values = set(freq.values())
			if len(values) == 1:
				return True
			if x in freq:
				freq[x] += 1
			else:
				freq[x] = 1
		return False


class Solution:

	def sameFreq(self, s):
		fre = {}
		for i in s:
			if i not in fre:
				fre[i] = 1
			else:
				fre[i] += 1
		flag = 0
		count = 0
		for i in fre:
			if fre[i] == count:
				break
			count = fre[i]
		if len(fre) == 2:
			count = -1
			for i in fre:
				count = max(count, fre[i])
		flag = 0
		for i in fre:
			if fre[i] == count:
				continue
			if fre[i] != count:
				if fre[i] == 1 or fre[i] - 1 == count:
					if flag == 0:
						flag = 1
						continue
					else:
						return False
			if fre[i] - 1 > count or fre[i] < count:
				return False
		return True


from collections import Counter

class Solution:

	def sameFreq(self, s):
		C = Counter(s)
		counts = []
		for i in C:
			counts.append(C[i])
		m = min(counts)
		cnt = 0
		for i in range(len(counts)):
			counts[i] -= m
			cnt += counts[i]
		if cnt <= 1:
			return 1
		if m == 1 and counts.count(0) == 1:
			m = 1000000000.0
			for i in range(len(counts)):
				if counts[i] != 0:
					m = min(m, counts[i])
			cnt = 0
			for i in range(len(counts)):
				counts[i] -= m
				cnt += max(0, counts[i])
			if cnt == 0:
				return 1
			return 0
		return 0


from collections import Counter

class Solution:

	def sameFreq(self, s):
		noofletwithocc = {}
		C = Counter(s)
		for i in C:
			try:
				noofletwithocc[C[i]] += 1
			except:
				noofletwithocc[C[i]] = 1
		if len(noofletwithocc) == 1:
			return 1
		elif len(noofletwithocc) > 2:
			return 0
		else:
			noofletwithocc_lst = []
			for i in noofletwithocc:
				noofletwithocc_lst.append([i, noofletwithocc[i]])
			if noofletwithocc_lst[0][0] == 1 and noofletwithocc_lst[0][1] == 1:
				return 1
			if noofletwithocc_lst[1][0] == 1 and noofletwithocc_lst[1][1] == 1:
				return 1
			if abs(noofletwithocc_lst[0][0] - noofletwithocc_lst[1][0]) == 1 and (noofletwithocc_lst[0][1] == 1 or noofletwithocc_lst[1][1] == 1):
				return 1
			else:
				return 0


from collections import Counter

class Solution:

	def sameFreq(self, s):
		c = Counter(s)
		values = list(Counter(c.values()).items())
		values.sort(reverse=True)
		values.sort(key=lambda x: x[1], reverse=True)
		n = len(values)
		if n > 2:
			return False
		if n == 1:
			return True
		if values[1] == (1, 1):
			return True
		if values[1][1] == 1 and values[1][0] - values[0][0] == 1:
			return True
		return False


class Solution:

	def sameFreq(self, s):
		d = {}
		n = 0
		for i in s:
			if not d.get(i):
				d[i] = 1
				n += 1
			else:
				d[i] += 1
		l = list(d.values())
		(a, b) = (min(l), max(l))
		if a == b:
			return True
		(x, y) = (l.count(a), l.count(b))
		if x == 1 and y == n - 1:
			return True
		if x == n - 1 and y == 1 and (b - a == 1):
			return True
		return False


class Solution:

	def sameFreq(self, s):
		st = {}
		for i in s:
			if i in st.keys():
				st[i] = st[i] + 1
			else:
				st[i] = 1
		mini = len(s)
		maxi = 0
		count1 = 0
		t = set()
		for (key, val) in st.items():
			t.add(val)
			if val == 1:
				count1 = count1 + 1
			if val < mini:
				mini = val
			if val > maxi:
				maxi = val
		if len(t) == 2 and count1 == 1:
			return 1
		if maxi - mini == 1 or mini - maxi == 0:
			return 1
		else:
			return 0


class Solution:

	def sameFreq(self, s):
		from collections import Counter
		count = Counter(s)
		freq = {}
		for key in count:
			if count[key] not in freq:
				freq[count[key]] = []
			freq[count[key]].append(key)
		if len(freq) == 1:
			return 1
		if len(freq) > 2:
			return 0
		(f1, f2) = list(freq.keys())
		if len(freq[f1]) > len(freq[f2]):
			majority = f1
			minority = f2
		else:
			majority = f2
			minority = f1
		if minority - 1 == majority or minority - 1 == 0:
			return 1
		return 0


from collections import Counter

class Solution:

	def sameFreq(self, s):
		n = len(s)
		if n == 0:
			return True
		freq = Counter(s)
		new_freq = Counter(freq.values())
		my_set = set(freq.values())
		if len(my_set) == 1:
			return True
		if len(my_set) == 2:
			if min(my_set) == 1 and new_freq[min(my_set)] == 1:
				return True
			if max(my_set) - min(my_set) == 1 and new_freq[max(my_set)] == 1:
				return True
		return False


class Solution:

	def sameFreq(self, s):
		n = len(s)
		if n < 3:
			return True
		d1 = {}
		d = {}
		for char in s:
			d1[char] = d1.get(char, 0) + 1
		for (key, value) in d1.items():
			d[value] = d.get(value, 0) + 1
		d_len = len(d)
		if d_len == 1:
			return True
		if d_len > 2:
			return False
		if d_len == 2:
			((key1, val1), (key2, val2)) = d.items()
			if key1 - key2 == 1:
				if val1 == 1:
					return True
			if key2 - key1 == 1:
				if val2 == 1:
					return True
			if key1 == 1 and val1 == 1:
				return True
			if key2 == 1 and val2 == 1:
				return True
		return False


class Solution:

	def sameFreq(self, s):
		d = {}
		l = []
		for i in s:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		for (k, v) in d.items():
			l.append(v)
		l.sort()
		if l[0] == l[-1]:
			return 1
		elif l[-1] - 1 == l[0]:
			return 1
		elif l[0] - 1 == 0 and l[1] == l[-1]:
			return 1


class Solution:

	def sameFreq(self, s):
		from collections import Counter
		freq = Counter(s)
		if len(set(freq.values())) == 1:
			return True
		else:
			freq = list(freq.values())
			for i in range(len(freq)):
				freq[i] -= 1
				if allSame(freq):
					return True
				else:
					freq[i] += 1
			return False

def allSame(arr):
	value = -1
	i = 0
	while i < len(arr) and arr[i] == 0:
		i += 1
	if i == len(arr):
		return True
	else:
		value = arr[i]
	for j in range(i + 1, len(arr)):
		if arr[j] != 0 and arr[j] != value:
			return False
	return True


class Solution:

	def sameFreq(self, s):
		d = {}
		for i in s:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		flag = False
		freqs_ = set(d.values())
		if len(freqs_) == 1:
			flag = True
		elif len(freqs_) == 2:
			freqs_ = list(freqs_)
			if max(freqs_) == min(freqs_) + 1:
				flag = True
			elif min(freqs_) == 1:
				flag = True
		return flag


class Solution:

	def sameFreq(self, s):
		charArr = [0] * 26
		for i in s:
			x = ord(i) - 97
			charArr[x] += 1
		numArr = {}
		for i in charArr:
			if i in numArr:
				numArr[i] += 1
			elif i == 0:
				continue
			elif len(numArr) > 2:
				return False
			else:
				numArr[i] = 1
		if len(numArr) == 1:
			return True
		smaller = 0
		for (key, value) in numArr.items():
			bigger = key
			if smaller == 0:
				smaller = bigger
		if smaller > bigger:
			(smaller, bigger) = (bigger, smaller)
		if numArr[smaller] == 1:
			return True
		if numArr[smaller] == numArr[bigger]:
			if bigger - smaller == 1:
				return True
			else:
				return False
		if numArr[smaller] > numArr[bigger]:
			if bigger - smaller == 1:
				return True
			else:
				return False
		else:
			return False


from collections import defaultdict

class Solution:

	def sameFreq(self, s):
		freqs = defaultdict(lambda : 0)
		for ch in s:
			freqs[ch] += 1
		ret_val = False
		freqs_ = set(freqs.values())
		if len(freqs_) == 1:
			ret_val = True
		elif len(freqs_) == 2:
			freqs_ = list(freqs_)
			if max(freqs_) == min(freqs_) + 1:
				ret_val = True
			elif min(freqs_) == 1:
				ret_val = True
		return ret_val


class Solution:

	def sameFreq(self, s):
		m = {}
		for i in s:
			if i not in m:
				m[i] = 1
			else:
				m[i] += 1
		s = set()
		for i in m:
			s.add(m[i])
		if len(s) == 1:
			return 1
		if len(s) > 2:
			return 0
		ans = []
		for i in s:
			if i == 1:
				return 1
			else:
				ans.append(i)
		if abs(ans[1] - ans[0]) == 1:
			return 1
		return 0


class Solution:

	def sameFreq(self, s):
		d = {}
		for i in s:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		l = list(d.values())
		se = set(l)
		l1 = list(se)
		if len(l1) == 1:
			return True
		elif len(l1) == 2:
			if l1[0] == 1 or l1[1] == 1 or abs(l1[0] - l1[1]) == 1:
				return True
		else:
			return False


class Solution:

	def sameFreq(self, s):
		d = {}
		for i in s:
			d[i] = d.get(i, 0) + 1
		l = list(d.values())
		n = len(l)
		(a, b) = (999999, -999999)
		d = {}
		for i in l:
			d[i] = d.get(i, 0) + 1
			if i < a:
				a = i
			if i > b:
				b = i
		if a == b:
			return True
		(c, d) = (d[a], d[b])
		if c == 1 and d == n - 1:
			return True
		if c == n - 1 and d == 1 and (b - a == 1):
			return True
		return False


class Solution:

	def sameFreq(self, s):
		map1 = [0] * 26
		n = len(s)
		for i in s:
			map1[ord(i) - ord('a')] += 1
		i = 0
		for i in range(26):
			if map1[i] != 0:
				break
		if map1[i] == n:
			return True
		j = i + 1
		for j in range(i + 1, 26):
			if map1[j] != 0:
				break
		if map1[i] + map1[j] == n:
			if abs(map1[i] - map1[j]) == 1 or abs(map1[i] - map1[j]) == 0 or map1[i] == 1 or (map1[j] == 1):
				return True
			return False
		k = j + 1
		for k in range(j + 1, 26):
			if map1[k] != 0:
				break
		if map1[i] + map1[j] + map1[k] == n and map1[i] == map1[j] and (map1[i] == map1[k]):
			return True
		if map1[i] != map1[j] and map1[i] != map1[k] and (map1[k] != map1[j]):
			return False
		if map1[i] == map1[j]:
			p = map1[i]
		elif map1[i] == map1[k]:
			p = map1[i]
		elif map1[k] == map1[j]:
			p = map1[k]
		h = 0
		for i in range(26):
			if h > 1:
				return False
			if map1[i] > 0 and abs(p - map1[i]) > 1 and (map1[i] > 1):
				return False
			if map1[i] > 0 and abs(p - map1[i]) > 1 and (map1[i] == 1):
				h += 1
			elif map1[i] > 0 and abs(p - map1[i]) == 1:
				h += 1
		if h > 1:
			return False
		return True


from collections import Counter

class Solution:

	def sameFreq(self, s):
		b = []
		a = []
		for i in s:
			b.append(i)
		c = Counter(b).most_common()
		for i in range(0, len(c)):
			a.append(c[i][1])
		k = Counter(a).most_common()
		if len(k) == 1:
			return 1
		elif len(k) == 2 and abs(k[0][0] - k[1][0]) == 1:
			return 1
		elif len(k) == 2 and 1 in [k[0][0], k[1][0]]:
			return 1
		else:
			return 0


class Solution:

	def sameFreq(self, s):
		dic = dict()
		for i in s:
			dic[i] = 1 + dic.get(i, 0)
		lst = list(set(list(dic.values())))
		if len(lst) == 1:
			return True
		elif len(lst) == 2:
			if min(lst) != 1 and abs(lst[1] - lst[0]) > 1:
				return False
			else:
				return True
		else:
			return False


class Solution:

	def sameFreq(self, s):
		d = {}
		for i in s:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		l = []
		count = 0
		aa = len(d)
		for i in d:
			l.append(d[i])
		ss = set(l)
		ll = list(ss)
		if len(ll) == 1:
			return True
		elif len(ll) == 2:
			if ll[0] == 1 or ll[1] == 1 or abs(ll[0] - ll[1]) == 1:
				return True
		else:
			return False


class Solution:

	def sameFreq(self, s):
		d = {}
		for i in s:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		l = list(set(d.values()))
		n = len(l)
		if n > 2:
			return 0
		if n == 0 or n == 1:
			return 1
		elif abs(l[1] - l[0]) == 1 or l[1] == 1 or l[0] == 1:
			return 1
		else:
			return 0


import math

class Solution:

	def sameFreq(self, s):
		d = dict()
		for x in s:
			if x in d:
				d[x] = d[x] + 1
			else:
				d[x] = 1
		l1 = list(set(d.values()))
		if len(l1) == 1:
			return True
		elif len(l1) == 2:
			if abs(l1[0] - l1[1]) == 1:
				return True
			elif abs(l1[0] - l1[1]) > 1:
				if l1[0] == 1 or l1[1] == 1:
					return True
		return False


class Solution:

	def sameFreq(self, s):
		from queue import PriorityQueue
		pq = PriorityQueue()
		d = {}
		for x in s:
			if x not in d:
				d[x] = 0
			d[x] += 1
		for x in d:
			pq.put(-d[x])
		prev = pq.get()
		count = 0
		ones = 0
		while not pq.empty():
			curr = pq.get()
			if abs(curr - prev) == 0:
				continue
			if abs(curr - prev) == 1:
				count += 1
			elif curr == -1:
				if ones > 1:
					return 0
				ones += 1
			else:
				return 0
			if count > 1:
				return 0
			prev = curr
		return 1


class Solution:

	def sameFreq(self, s):
		d = {}
		for i in s:
			try:
				d[i] += 1
			except:
				d[i] = 1
		s = set()
		for i in d:
			if d[i] not in s:
				s.add(d[i])
		if len(s) > 2:
			return 0
		if len(s) == 1:
			return 1
		s = list(s)
		if abs(s[0] - s[1]) == 1 or min(s) == 1:
			return 1
		return 0


class Solution:

	def sameFreq(self, s):
		dic = {}
		arr = []
		for i in s:
			if i not in dic:
				dic[i] = 1
			else:
				dic[i] += 1
		for j in dic.values():
			arr.append(j)
		if len(arr) == 2:
			if arr[0] == arr[1]:
				return True
			elif abs(arr[0] - arr[1]) == 1:
				return True
			elif arr[0] == 1 or arr[1] == 1:
				return True
			else:
				return False
		ele = max(set(arr), key=arr.count)
		if arr.count(ele) == len(arr):
			return True
		elif arr.count(ele) == len(arr) - 1:
			arr.sort()
			if arr[0] == ele:
				if arr[-1] - arr[0] == 1:
					return True
				else:
					return False
			elif arr[-1] == ele:
				if arr[0] == 1:
					return True
				else:
					return False
		else:
			return False


from collections import Counter

class Solution:

	def sameFreq(self, string):
		count_dict = dict(Counter(string))
		values = list(count_dict.values())
		(min_values, max_values) = (min(values), max(values))
		return all([values[0] == v for v in values]) == True or values.count(max_values) == len(values) - 1 or (values.count(min_values) == len(values) - 1 and max_values - min_values == 1)


class Solution:

	def sameFreq(self, s):
		dic = {}
		for i in s:
			if i in dic:
				dic[i] += 1
			else:
				dic[i] = 1
		List = list(dic.values())
		a = min(dic.values())
		b = max(dic.values())
		n = len(List)
		if a == b:
			return 1
		x = List.count(a)
		y = List.count(b)
		if x == 1 and y == n - 1:
			return 1
		if x == n - 1 and y == 1 and (b - a == 1):
			return 1
		return 0


class Solution:

	def getIdx(self, ch):
		return ord(ch) - ord('a')

	def allSame(self, freq, N):
		for i in range(0, N):
			if freq[i] > 0:
				same = freq[i]
				break
		for j in range(i + 1, N):
			if freq[j] > 0 and freq[j] != same:
				return False
		return True

	def sameFreq(self, s):
		l = len(s)
		freq = [0] * 26
		for i in range(0, l):
			freq[self.getIdx(s[i])] += 1
		if self.allSame(freq, 26):
			return True
		for i in range(0, 26):
			if freq[i] > 0:
				freq[i] -= 1
				if self.allSame(freq, 26):
					return 1
				freq[i] += 1
		return 0


class Solution:

	def sameFreq(self, s):
		d = {}
		res = 0
		for i in s:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		val = []
		for i in d.values():
			val.append(i)
		if len(set(val)) == 1:
			res = 1
		elif len(set(val)) == 2:
			if 1 in val:
				res = 1
			if max(val) - min(val) == 1:
				res = 1
		return res


class Solution:

	def sameFreq(self, s):
		a = {}
		for i in range(len(s)):
			a[s[i]] = 0
		for i in range(len(s)):
			a[s[i]] += 1
		aa = []
		for k in a:
			aa.append(a[k])
		mi = min(aa)
		tt = 0
		kk = 0
		su = 0
		c = 0
		for i in range(len(aa)):
			if aa[i] == mi:
				tt += 1
			elif kk == 0:
				c = aa[i]
				kk += 1
			elif c == aa[i]:
				kk += 1
			su += aa[i] - mi
		if su <= 1 or (mi == 1 and tt + kk == len(aa)):
			return 1
		else:
			return 0


class Solution:

	def sameFreq(self, s):
		freq = []
		s_new = ''
		sum = 0
		for i in range(len(s)):
			if s[i] not in s_new:
				s_new = s_new + s[i]
				freq = freq + [s.count(s[i])]
		a = freq[0]
		flag = 0
		for i in range(1, len(freq)):
			if freq[i] != a:
				if a == 1 and freq.count(freq[i]) == len(freq) - 1:
					freq = freq[1:len(freq)]
					break
				elif freq[i] == 1 and freq.count(a) == len(freq) - 1:
					freq = freq[0:i] + freq[i + 1:len(freq)]
					break
				elif a > freq[i]:
					freq[0] = freq[0] - 1
					break
				elif a < freq[i]:
					freq[i] = freq[i] - 1
					break
		a1 = freq[0]
		if freq.count(a1) == len(freq):
			return 1
		return 0


class Solution:

	def sameFreq(self, s):
		h = {}
		for a in s:
			if a in h:
				h[a] += 1
			else:
				h[a] = 1
		vals = []
		count1 = None
		count2 = None
		for a in h:
			v = h[a]
			if count1 is not None and count1 == v:
				continue
			elif count2 is not None and count2 == v:
				continue
			elif count1 is None:
				count1 = v
			elif count2 is None:
				count2 = v
			else:
				return 0
		if count2 is None:
			return 1
		if count1 == count2 + 1 or count1 == count2 - 1 or count2 == 1 or (count1 == 1):
			return 1
		return 0


class Solution:

	def sameFreq(self, s):
		dic = {}
		for i in s:
			if i not in dic:
				dic[i] = 1
			else:
				dic[i] += 1
		lis = list(dic.values())
		if len(set(lis)) == 1:
			return 1
		else:
			tit = list(set(lis))
			if len(tit) == 2:
				if 1 in tit:
					return 1
				if max(tit) - min(tit) == 1:
					return 1
		return 0


class Solution:

	def sameFreq(self, s):
		d = {}
		for ele in s:
			if ele not in d:
				d[ele] = 1
			else:
				d[ele] += 1
		count_set = set(d.values())
		d = len(count_set)
		if d > 2:
			return False
		if d == 2:
			x = list(count_set)
			if abs(x[0] - x[1]) == 1:
				return True
			elif x[0] == 1 or x[1] == 1:
				return True
			else:
				return False
		if d == 1:
			return True


class Solution:

	def sameFreq(self, s):
		m = {}
		for i in s:
			if i in m:
				m[i] += 1
			else:
				m[i] = 1
		s = 0
		f = 0
		for j in m:
			if s == 0:
				s = m[j]
			elif s != m[j]:
				f = 1
				break
		if f == 0:
			return True
		for i in m:
			m[i] -= 1
			f = 0
			s = 0
			for j in m:
				if m[j] != 0 and s == 0:
					s = m[j]
				elif s != 0 and m[j] != 0:
					if s != m[j]:
						f = 1
						break
				else:
					pass
			if f == 0:
				return True
			m[i] += 1
		return False


from collections import Counter

class Solution:

	def sameFreq(self, s):
		l1 = Counter(s)
		value = l1.most_common(1)[0][1]
		dict1 = {}
		for i in l1:
			dict1[i] = l1[i]
		s1 = set(dict1.values())
		length = len(s1)
		if len(s1) == 1:
			return True
		for i in dict1.values():
			if i == 1 and length == 2:
				return True
			if i != value:
				if abs(i - value) == 1 and length == 2:
					return True
		return False


class Solution:

	def sameFreq(self, s):
		di = {}
		for c in s:
			if c in di:
				di[c] += 1
			else:
				di[c] = 1
		vals = list(set(di.values()))
		if len(vals) == 1:
			return True
		elif len(vals) > 2:
			return False
		elif abs(vals[0] - vals[1]) == 1:
			return True
		elif vals[0] == 1 or vals[1] == 1:
			return True
		else:
			return False


class Solution:

	def sameFreq(self, string):
		d = {}
		for s in string:
			d[s] = d.get(s, 0) + 1
		if len(set(d.values())) == 1:
			return 1
		arr = []
		if len(set(d.values())) == 2:
			for i in set(d.values()):
				arr.append(i)
			if arr[0] == 1 or arr[1] == 1:
				return 1
			elif abs(arr[0] - arr[1]) == 1:
				return 1
		return 0


class Solution:

	def sameFreq(self, s):

		def checkFreq(num_letters):
			check = True
			freq = None
			for j in num_letters:
				if num_letters[j] != 0:
					if freq is None:
						freq = num_letters[j]
					elif freq != num_letters[j]:
						check = False
						break
			return check
		num_letters = {}
		for i in s:
			if i not in num_letters:
				num_letters[i] = 0
			num_letters[i] += 1
		check = checkFreq(num_letters)
		if check == True:
			return True
		for k in num_letters:
			num_letters[k] -= 1
			check = checkFreq(num_letters)
			if check == True:
				return True
			num_letters[k] += 1


class Solution:

	def sameFreq(self, s):
		dic = {}
		for i in s:
			dic[i] = dic.get(i, 0) + 1
		con = 0
		l1 = list(dic.values())
		l2 = list(dic.values())
		if l1.count(l1[0]) == len(l1):
			return True
		for i in range(len(l1)):
			if l1.count(l1[i]) == 1:
				l2[i] = l1[i] - 1
				if l2[i] == 0:
					l2.remove(l2[i])
				break
		if l2.count(l2[0]) == len(l2):
			return True
		return False


class Solution:

	def sameFreq(self, s):
		dct = {}
		for i in s:
			if i not in dct:
				dct[i] = 1
			else:
				dct[i] += 1
		dct_counts = {}
		for key in dct:
			if dct[key] not in dct_counts:
				dct_counts[dct[key]] = 1
			else:
				dct_counts[dct[key]] += 1
		if len(dct_counts.keys()) > 2 or len(dct_counts.keys()) == 0:
			return 0
		if len(dct_counts.keys()) == 1:
			return 1
		(key1, key2) = dct_counts.keys()
		if (dct_counts[key1] == 1 or dct_counts[key2] == 1) and (abs(key1 - key2) < 2 or (key1 == dct_counts[key1] == 1 or key2 == dct_counts[key2] == 1)):
			return 1
		return 0


class Solution:

	def sameFreq(self, s):
		d = {}
		for i in s:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		lis = list(d.values())
		a = min(lis)
		b = max(lis)
		n = len(lis)
		if a == b:
			return 1
		x = lis.count(a)
		y = lis.count(b)
		if x == 1 and y == n - 1:
			return 1
		if x == n - 1 and y == 1 and (b - a == 1):
			return 1
		return 0


class Solution:

	def sameFreq(self, s):
		ls = []
		s1 = set(s)
		for x in s1:
			ls.append(s.count(x))
		k = {}
		for x in ls:
			if x in k.keys():
				k[x] += 1
			else:
				k[x] = 1
		if len(k) == 1:
			return 1
		elif len(k) > 2:
			return 0
		else:
			l = list(set(ls))
			l.sort()
			if abs(l[0] - l[1]) != 1:
				if l[0] == 1 and k[l[0]] == 1:
					return 1
				else:
					return 0
			elif k[l[1]] > 1:
				return 0
			else:
				return 1


class Solution:

	def sameFreq(self, s):
		d = {}
		for i in s:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		a = []
		for i in d:
			a.append(d[i])
		if len(a) == 1:
			return True
		temp = set(a)
		if len(temp) == 1:
			return True
		for i in range(len(a)):
			a[i] -= 1
			ele = a[(i + 1) % len(a)]
			flag = 0
			for j in range(len(a)):
				if a[j] == ele or (i == j and a[i] == 0):
					continue
				else:
					flag = 1
			if flag == 0:
				return True
			a[i] += 1
		return False


class Solution:
	M = 26

	def getidx(self, ch):
		return ord(ch) - ord('a')

	def isSame(self, freq, n):
		for i in range(0, n):
			if freq[i] > 0:
				same = freq[i]
				break
		for j in range(i + 1, n):
			if freq[j] > 0 and freq[j] != same:
				return 0
		return 1

	def sameFreq(self, s):
		l = len(s)
		freq = [0] * self.M
		for i in range(0, l):
			freq[self.getidx(s[i])] += 1
		if self.isSame(freq, self.M):
			return 1
		for i in range(0, self.M):
			if freq[i] > 0:
				freq[i] -= 1
				if self.isSame(freq, self.M):
					return 1
				freq[i] += 1
		return 0


class Solution:

	def sameFreq(self, s):
		ref_s = {}
		for x in s:
			if x not in ref_s:
				ref_s[x] = 1
			else:
				ref_s[x] += 1
		val1 = 0
		val2 = 0
		cnt1 = 0
		cnt2 = 0
		for x in ref_s:
			if val1 == 0:
				val1 = ref_s[x]
				cnt1 += 1
			elif ref_s[x] != val1:
				if val2 == 0:
					val2 = ref_s[x]
					cnt2 += 1
				elif ref_s[x] != val2:
					return False
				else:
					cnt2 += 1
			else:
				cnt1 += 1
		if val1 > 1 and val2 > 1:
			if abs(val1 - val2) > 1:
				return False
			elif cnt1 <= 1 or cnt2 <= 1:
				return True
			else:
				return False
		else:
			return True