Given a string S, return the sum of beauty of all its substrings.
The beauty of a string is defined as the difference in frequencies between the most frequent and least frequent characters.
	For example, the beauty of string "aaac" is 3 - 1 = 2.
Example 1:
Input:
S = "aaac"
Output: 
3
Explanation: The substrings with non - zero beauty are ["aaac","aac"] where beauty of "aaac" is 2 and beauty of "aac" is 1.
 
Example 2:
Input:
S = "geeksforgeeks"
Output: 
62
Explanation: There are 91 substrings of the given strings. Like, the beauty of substring "geek" is 1. In this way the sum of beauties of all substrings are 62.
Your Task:
You don't need to read input or print anything. Your task is to complete the function beautySum() which takes string S as input paramters and returns the sum of beauty of all its substrings. 
Expected Time Complexity: O(|S|^{2})
Expected Auxiliary Space: O(1)
Constraints: 
1 ≤ |S| ≤ 500
S only contains lower case alphabets.

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: String algorithms

Data structures

Starter code: #User function Template for python3



class Solution:

    def beautySum(self, s):

        # Code here

Solutions:
class Solution:

	def beautySum(self, s):
		(beauty, sum) = (0, 0)
		for i in range(len(s)):
			ch = {}
			for j in range(i, len(s)):
				ch.setdefault(s[j], 0)
				ch[s[j]] += 1
				beauty += max(ch.values()) - min(ch.values())
		return beauty


class Solution:

	def beautySum(self, s):
		summ = 0
		i = 0
		while s[i:]:
			S = s[i:]
			di = {}
			for ch in S:
				if ch in di.keys():
					di[ch] += 1
				else:
					di[ch] = 1
				summ += max(di.values()) - min(di.values())
			i += 1
		return summ


class Solution:

	def beautySum(self, s):
		beauty = 0
		n = len(s)
		for i in range(n):
			dic = {}
			for j in range(i, n):
				dic[s[j]] = dic.get(s[j], 0) + 1
				freq = dic.values()
				beauty += max(freq) - min(freq)
		return beauty


from collections import defaultdict

class Solution:

	def beautySum(self, s):
		ans = 0
		n = len(s)
		for i in range(n):
			fre = defaultdict(int)
			for j in range(i, n):
				fre[s[j]] += 1
				arr = fre.values()
				ans += max(arr) - min(arr)
		return ans


class Solution:

	def beautySum(self, s):
		ans = 0
		for i in range(len(s)):
			d = {}
			for j in range(i, len(s)):
				if s[j] in d:
					d[s[j]] += 1
				else:
					d[s[j]] = 1
				mf = max(d.values())
				lf = min(d.values())
				ans += mf - lf
		return ans


class Solution:

	def beautySum(self, s):
		res = 0
		n = len(s)
		for i in range(n):
			hashmap = {}
			for j in range(i, n):
				hashmap[s[j]] = 1 + hashmap.get(s[j], 0)
				res += max(hashmap.values()) - min(hashmap.values())
		return res


from collections import Counter

class Solution:

	def beautySum(self, s):
		n = len(s)
		ans = 0
		PI = float('inf')
		d = Counter()
		for i in range(n):
			d.clear()
			mxFreq = 0
			for j in range(i, n):
				d[s[j]] += 1
				mxFreq = max(mxFreq, d[s[j]])
				mnFreq = min(d.values())
				ans += mxFreq - mnFreq
		return ans


class Solution:

	def beautySum(self, s):
		ret = 0
		for i in range(len(s)):
			d = {}
			for j in range(i, len(s)):
				d.setdefault(s[j], 0)
				d[s[j]] += 1
				ret += max(d.values()) - min(d.values())
		return ret


class Solution:

	def beautySum(self, s: str) -> int:
		n = len(s)
		beauty_sum = 0
		for i in range(n):
			freq = {}
			for j in range(i, n):
				if s[j] not in freq:
					freq[s[j]] = 0
				freq[s[j]] += 1
				max_freq = max(freq.values())
				min_freq = min(freq.values())
				beauty_sum += max_freq - min_freq
		return beauty_sum


class Solution:

	def beautySum(self, s):
		su = 0
		for i in range(len(s)):
			dic = {}
			for j in range(i, len(s)):
				if s[j] in dic:
					dic[s[j]] += 1
				else:
					dic[s[j]] = 1
				su += max(dic.values()) - min(dic.values())
		return su


from collections import defaultdict

class Solution:

	def beautySum(self, s):
		ans = 0
		n = len(s)
		for i in range(n):
			count = {}
			temp = ''
			for j in range(i, n):
				temp += s[j]
				count[s[j]] = count.get(s[j], 0) + 1
				if len(count) > 1:
					ans += max(count.values()) - min(count.values())
		return ans


import collections

class Solution:

	def beautySum(self, s):
		ans = 0
		for i in range(len(s)):
			freq_groups = collections.defaultdict(int)
			char_freq = {}
			(max_freq, min_freq) = (1, 1)
			char_freq[s[i]] = 1
			freq_groups[char_freq[s[i]]] = 1
			for j in range(i + 1, len(s)):
				if s[j] not in char_freq:
					char_freq[s[j]] = 1
					min_freq = min(min_freq, 1)
					freq_groups[char_freq[s[j]]] += 1
					ans += max_freq - min_freq
				else:
					freq_groups[char_freq[s[j]]] -= 1
					if freq_groups[char_freq[s[j]]] == 0 and min_freq == char_freq[s[j]]:
						min_freq += 1
					char_freq[s[j]] += 1
					freq_groups[char_freq[s[j]]] += 1
					max_freq = max(char_freq[s[j]], max_freq)
					ans += max_freq - min_freq
		return ans


class Solution:

	def beautySum(self, s):
		total = 0
		length = len(s)
		for i in range(length - 1):
			dict1 = dict({s[i]: 1})
			count = 1
			maximum = 1
			for j in range(i + 1, length):
				if s[j] not in dict1:
					dict1[s[j]] = 1
					minimum = 1
					count += 1
				else:
					dict1[s[j]] += 1
					maximum = max(maximum, dict1[s[j]])
				minimum = min(dict1.values())
				if count >= 2:
					total += maximum - minimum
		return total


class Solution:

	def beautySum(self, s):
		beauty = 0
		for i in range(len(s)):
			ch = {}
			for j in range(i, len(s)):
				if s[j] in ch:
					ch[s[j]] += 1
				else:
					ch[s[j]] = 1
				beauty += max(ch.values()) - min(ch.values())
		return beauty


import collections

class Solution:

	def beautySum(self, s):
		ans = 0
		for i in range(len(s)):
			feq = collections.defaultdict(int)
			char_freq = {}
			char_freq[s[i]] = 1
			minn = 1
			maxx = 1
			feq[char_freq[s[i]]] = 1
			for j in range(i + 1, len(s)):
				if s[j] not in char_freq:
					char_freq[s[j]] = 1
					feq[char_freq[s[j]]] += 1
					minn = min(1, char_freq[s[i]])
					ans += maxx - minn
				else:
					feq[char_freq[s[j]]] -= 1
					if feq[char_freq[s[j]]] == 0 and minn == char_freq[s[j]]:
						minn += 1
					char_freq[s[j]] += 1
					feq[char_freq[s[j]]] += 1
					maxx = max(maxx, char_freq[s[j]])
					ans += maxx - minn
		return ans


class Solution:

	def beautySum(self, s):
		beauty = 0
		for i in range(len(s) - 2):
			Freq = {}
			for j in range(i, len(s)):
				Freq.setdefault(s[j], 0)
				Freq[s[j]] += 1
				beauty += max(Freq.values()) - min(Freq.values())
		return beauty


class Solution:

	def beautySum(self, s):
		answer = 0
		for i in range(len(s)):
			mp = {}
			for j in range(i, len(s)):
				if s[j] in mp.keys():
					mp[s[j]] += 1
				else:
					mp[s[j]] = 1
				ma = max(mp.values())
				mi = min(mp.values())
				answer += ma - mi
		return answer


class Solution:

	def beautySum(self, s):
		su = 0
		for i in range(len(s)):
			h = {}
			for j in range(i, len(s)):
				if s[j] not in h:
					h[s[j]] = 1
				else:
					h[s[j]] += 1
				ma = max(h.values())
				mn = min(h.values())
				su += ma - mn
		return su


class Solution:

	def beautySum(self, s):
		maxi = 0
		mini = 0
		result = 0
		for i in range(len(s)):
			d = {}
			for j in range(i, len(s)):
				if s[j] in d:
					d[s[j]] += 1
				else:
					d[s[j]] = 1
				maxi = max(d.values())
				mini = min(d.values())
				if maxi - mini > 0:
					result = result + (maxi - mini)
		return result


from collections import Counter

class Solution:

	def beautySum(self, s):
		(beauty, sum) = (0, 0)
		for i in range(len(s)):
			ch = {}
			for j in range(i, len(s)):
				ch.setdefault(s[j], 0)
				ch[s[j]] += 1
				beauty += max(ch.values()) - min(ch.values())
		return beauty


class Solution:

	def beautySum(self, s):
		(ans, sum) = (0, 0)
		for i in range(len(s)):
			dic = {}
			for j in range(i, len(s)):
				dic.setdefault(s[j], 0)
				dic[s[j]] += 1
				ans += max(dic.values()) - min(dic.values())
		return ans


class Solution:

	def beautySum(self, s):
		ans = 0
		n = len(s)
		for i in range(n):
			d = {}
			for j in range(i, n):
				if s[j] in d:
					d[s[j]] += 1
				else:
					d[s[j]] = 1
				ma = max(d.values())
				mi = min(d.values())
				ans = ans + (ma - mi)
		return ans


from collections import Counter

class Solution:

	def beautySum(self, s):
		res = 0
		for i in range(len(s)):
			count = Counter()
			for j in range(i, len(s)):
				count[s[j]] = count[s[j]] + 1
				res = res + max(count.values()) - min(count.values())
		return res


class Solution:

	def beautySum(self, s):
		x = 0
		n = len(s)
		for i in range(n - 2):
			f = {}
			for j in range(i, n):
				if s[j] in f:
					f[s[j]] += 1
				else:
					f[s[j]] = 1
				x += max(f.values()) - min(f.values())
		return x


from collections import Counter
from itertools import combinations

class Solution:

	def beautySum(self, s):
		su = 0
		for i in range(len(s)):
			d = {}
			for j in range(i, len(s)):
				if s[j] not in d:
					d[s[j]] = 1
				else:
					d[s[j]] += 1
				su += max(d.values()) - min(d.values())
		return su


class Solution:

	def beautySum(self, s):
		diff = 0
		for i in range(len(s)):
			dic = dict()
			for j in range(i, len(s)):
				if s[j] not in dic:
					dic[s[j]] = 0
				else:
					dic[s[j]] += 1
				diff += max(dic.values()) - min(dic.values())
		return diff


class Solution:

	def beautySum(self, s):
		n = len(s)
		sum_beauty = 0
		for i in range(n):
			d = {}
			for j in range(i, n):
				if s[j] in d:
					d[s[j]] += 1
				else:
					d[s[j]] = 1
				max_frq = max(d.values())
				min_frq = min(d.values())
				sum_beauty += max_frq - min_frq
		return sum_beauty


class Solution:

	def beautySum(self, s):
		count = 0
		for i in range(len(s)):
			z = {}
			z[s[i]] = 1
			(mx, mn) = (1, 1)
			for j in range(i + 1, len(s)):
				if s[j] not in z:
					z[s[j]] = 1
				else:
					z[s[j]] += 1
				mx = max(z[s[j]], mx)
				mn = min(z.values())
				count += mx - mn
		return count


from collections import defaultdict

class Solution:

	def beautySum(self, s):
		(ans, n) = (0, len(s))
		for i in range(n):
			char_count_map = defaultdict(int)
			count_char_map = defaultdict(set)
			min_cnt = max_cnt = 0
			for j in range(i, n):
				c = s[j]
				char_count_map[c] += 1
				char_count = char_count_map[c]
				count_char_map[char_count].add(c)
				if char_count > 1:
					count_char_map[char_count - 1].remove(c)
				max_cnt = max(max_cnt, char_count)
				if char_count < min_cnt:
					min_cnt = char_count
				elif not count_char_map[min_cnt]:
					min_cnt = char_count
				ans += max_cnt - min_cnt
		return ans


class Solution:

	def beautySum(self, s):
		answer = 0
		for i in range(len(s)):
			hist = [0] * 26
			maxF = 0
			minF = 1
			for c in s[i:]:
				jj = ord(c) - ord('a')
				hist[jj] += 1
				maxF = max(maxF, hist[jj])
				if hist[jj] - 1 == minF:
					minF = min((x for x in hist if x > 0))
				else:
					minF = min(minF, hist[jj])
				answer += maxF - minF
		return answer


class Solution:

	def beautySum(self, s):
		n = len(s)
		ans = 0
		for i in range(n):
			ch = {}
			for j in range(i, n):
				ch.setdefault(s[j], 0)
				ch[s[j]] += 1
				ans += max(ch.values()) - min(ch.values())
		return ans


class Solution:

	def beautySum(self, s):
		n = len(s)
		sum = 0
		letter_dict = {}
		for start in range(n - 2):
			for stop in range(start, n):
				letter_dict.setdefault(s[stop], 0)
				letter_dict[s[stop]] += 1
				values = letter_dict.values()
				sum += max(values) - min(values)
			letter_dict.clear()
		return sum


from collections import defaultdict

class Solution:

	def beautySum(self, s):
		n = len(s)
		ans = 0
		for i in range(len(s)):
			f = defaultdict(int)
			ff = defaultdict(int)
			maxf = 0
			minf = 1
			for j in range(i, len(s)):
				ff[f[s[j]]] -= 1
				f[s[j]] += 1
				ff[f[s[j]]] += 1
				minf = min(minf, f[s[j]])
				if ff[minf] == 0:
					minf += 1
				maxf = max(maxf, f[s[j]])
				ans += maxf - minf
		return ans


from collections import defaultdict

class Solution:

	def beautySum(self, s):
		beauty = 0
		len_s = len(s)
		for start in range(len_s - 1):
			chars_freq = defaultdict(int)
			chars_freq[s[start]] += 1
			for end in range(start + 1, len_s):
				chars_freq[s[end]] += 1
				beauty += max(chars_freq.values()) - min(chars_freq.values())
		return beauty


class Solution:

	def beautySum(self, s):
		res = 0
		for i in range(len(s)):
			d = {}
			for j in range(i, len(s)):
				if s[j] not in d:
					d[s[j]] = 1
				else:
					d[s[j]] = d[s[j]] + 1
				res += max(d.values()) - min(d.values())
		return res


class Solution:

	def beautySum(self, s):
		n = len(s)
		sum = 0
		for i in range(n):
			dict = {}
			for j in range(i, n):
				dict.setdefault(s[j], 0)
				dict[s[j]] += 1
				sum += max(dict.values()) - min(dict.values())
		return sum


class Solution:

	def beautySum(self, s):
		ans = 0
		n = len(s)
		for i in range(n):
			map = {}
			for j in range(i, n):
				if s[j] not in map:
					map[s[j]] = 0
				map[s[j]] += 1
				ans += max(map.values()) - min(map.values())
		return ans


class Solution:

	def beautySum(self, s):
		result = 0
		for i in range(len(s)):
			S = {}
			for j in range(i, len(s)):
				if s[j] not in S:
					S[s[j]] = 1
				else:
					S[s[j]] += 1
				(mostFrequency, leastFrequency) = (max(S.values()), min(S.values()))
				result += mostFrequency - leastFrequency
		return result


import math
from collections import defaultdict

class Solution:

	def beautySum(self, s):
		(beauty, sz) = (0, len(s))
		for left in range(sz):
			freqHash = defaultdict(int)
			for right in range(left, sz):
				freqHash[s[right]] += 1
				beauty += max(freqHash.values()) - min(freqHash.values())
		return beauty


class Solution:

	def beautySum(self, s):
		b = 0
		for i in range(len(s)):
			d = {}
			for j in range(i, len(s)):
				try:
					d[s[j]] += 1
				except:
					d[s[j]] = 1
				b += max(d.values()) - min(d.values())
		return b