Given a string S. The task is to count the number of substrings which contains equal number of lowercase and uppercase letters. 
Example 1:
Input:
S = "gEEk"
Output: 3
Explanation: There are 3 substrings of
the given string which satisfy the
condition. They are "gE", "gEEk" and "Ek".
Example 2:
Input:
S = "WomensDAY"
Output: 4
Explanation: There are 4 substrings of 
the given string which satisfy the
condition. They are "Wo", "ensDAY", 
"nsDA" and "sD"
Your Task:
The task is to complete the function countSubstring() which takes the string S as input parameter and returns the number of substrings which contains equal number of uppercase and lowercase letters.
Expected Time Complexity: O(N*N)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ |S| ≤ 10^{3}

Source: geeksforgeeks | Difficulty: EASY
Tags: String algorithms

Data structures

Starter code: #User function Template for python3

class Solution:

    def countSubstring(self, S): 

        #code here

Solutions:
class Solution:

	def countSubstring(self, S):
		count = 0
		for i in range(len(S)):
			upper = 0
			lower = 0
			if S[i].isupper():
				upper += 1
			else:
				lower += 1
			for j in range(i + 1, len(S)):
				if S[j].isupper():
					upper += 1
				else:
					lower += 1
				if upper == lower:
					count += 1
		return count


class Solution:

	def countSubstring(self, S):
		sum = 0
		for x in range(len(S)):
			(val, b) = (0, 0)
			for y in range(x, len(S)):
				if S[y].islower():
					val += 1
				else:
					b += 1
				if val == b:
					sum += 1
		return sum


class Solution:

	def countSubstring(self, s):
		result = 0
		for i in range(0, len(s)):
			upper = 0
			lower = 0
			for j in range(i, len(s)):
				if s[j] >= 'A' and s[j] <= 'Z':
					upper += 1
				else:
					lower += 1
				if upper == lower:
					result += 1
		return result


class Solution:

	def countSubstring(self, S):
		r = 0
		for i in range(0, len(S)):
			l = 0
			u = 0
			for j in range(i, len(S)):
				if S[j] >= 'a' and S[j] <= 'z':
					l = l + 1
				else:
					u = u + 1
				if l == u:
					r = r + 1
		return r


class Solution:

	def countSubstring(self, S):
		n = len(S)
		count = 0
		for i in range(n):
			(l, u) = (0, 0)
			for j in range(i, n):
				if S[j].islower():
					l += 1
				else:
					u += 1
				if l == u:
					count += 1
		return count


class Solution:

	def countSubstring(self, S):
		case_codes = [1 if c.islower() else -1 for c in S]
		sum_counts = {}
		cur_sum = 0
		num_eq_substr = 0
		for code in case_codes:
			cur_sum += code
			if cur_sum == 0:
				num_eq_substr += 1
			prev_count = sum_counts.get(cur_sum, 0)
			num_eq_substr += prev_count
			sum_counts[cur_sum] = prev_count + 1
		return num_eq_substr
import operator as op
from functools import reduce

def ncr(n, r):
	r = min(r, n - r)
	numer = reduce(op.mul, range(n, n - r, -1), 1)
	denom = reduce(op.mul, range(1, r + 1), 1)
	return numer // denom


class Solution:

	def countSubstring(self, S):
		case_codes = [1 if c.islower() else -1 for c in S]
		num_eq_substr = 0
		for i in range(0, len(S) - 1):
			cur_sum = case_codes[i]
			for j in range(i + 1, len(S)):
				cur_sum += case_codes[j]
				if cur_sum == 0:
					num_eq_substr += 1
		return num_eq_substr


class Solution:

	def countSubstring(self, S):
		if len(S) <= 1:
			return 0
		uppercase_letters = ('A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z')
		lowercase_letters = ('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z')
		count = 0
		for i in range(len(S)):
			c = S[i]
			lowercase_count = 0
			uppercase_count = 0
			if c in lowercase_letters:
				lowercase_count += 1
			else:
				uppercase_count += 1
			for j in range(i + 1, len(S)):
				d = S[j]
				if d in lowercase_letters:
					lowercase_count += 1
				else:
					uppercase_count += 1
				if lowercase_count == uppercase_count:
					count += 1
		return count


class Solution:

	def countSubstring(self, S):
		c = 0
		for i in range(0, len(S)):
			low = 0
			up = 0
			for j in range(i, len(S)):
				if S[j].isupper():
					up += 1
				else:
					low += 1
				if up == low:
					c += 1
		return c


class Solution:

	def countSubstring(self, s):
		n = len(s)
		a = [0] * n
		for i in range(n):
			if s[i].isupper():
				a[i] = 1
			else:
				a[i] = -1
		st = {}
		st[0] = 1
		tc = 0
		s = 0
		for i in range(n):
			s += a[i]
			if s not in st:
				st[s] = 1
			else:
				tc += st.get(s)
				st[s] += 1
		return tc


class Solution:

	def countSubstring(self, s):
		tc = 0
		n = len(s)
		for i in range(n):
			lc = 0
			uc = 0
			for j in range(i, n):
				if s[j].isupper():
					uc += 1
				else:
					lc += 1
				if uc == lc:
					tc += 1
		return tc


import collections

class Solution:

	def countSubstring(self, S):
		bal = 0
		hm = collections.defaultdict(int)
		ans = 0
		hm[0] = 1
		for i in range(len(S)):
			if S[i] >= 'a' and S[i] <= 'z':
				bal += 1
			else:
				bal -= 1
			if bal in hm:
				ans += hm[bal]
			hm[bal] += 1
		return ans


class Solution:

	def countSubstring(self, S):
		from collections import defaultdict
		b = defaultdict(int)
		ret = 0
		for i in range(len(S)):
			s = S[i]
			if s == s.lower():
				b[i] = b[i - 1] + 1
			else:
				b[i] = b[i - 1] - 1
			for j in range(i - 1, -1, -2):
				if b[i] - b[j - 1] == 0:
					ret += 1
		return ret


class Solution:

	def countSubstring(self, S):
		from collections import defaultdict
		l = defaultdict(int)
		n = len(S)
		ret = 0
		for i in range(n):
			l[i] = l[i - 1]
			if S[i] == S[i].lower():
				l[i] += 1
			for j in range(i - 1, -1, -2):
				if l[i] - l[j - 1] == i - l[i] - (j - 1 - l[j - 1]):
					ret += 1
		return ret


class Solution:

	def countSubstring(self, S):
		r = 0
		for i in range(len(S)):
			lower = 0
			upper = 0
			for j in range(i, len(S)):
				if S[j] >= 'a' and S[j] <= 'z':
					lower = lower + 1
				else:
					upper = upper + 1
				if lower == upper:
					r = r + 1
		return r


class Solution:

	def countSubstring(self, S):
		count = 0
		i = 0
		n = len(S)
		while i < n:
			lc = 0
			uc = 0
			j = i
			while j < n:
				if S[j].islower():
					lc += 1
				else:
					uc += 1
				if lc == uc:
					count += 1
				j += 1
			i += 1
		return count


class Solution:

	def countSubstring(self, S):
		count = 0
		low = 0
		upp = 0
		for i in range(len(S)):
			low = 0
			upp = 0
			for j in range(i, len(S)):
				if S[j].islower():
					low += 1
				else:
					upp += 1
				if low == upp:
					count += 1
		return count


class Solution:

	def countSubstring(self, S):
		count = 0
		for i in range(len(S)):
			(l, r) = (0, 0)
			for j in range(i, len(S)):
				if S[j].isupper():
					r += 1
				elif S[j].islower():
					l += 1
				if l == r:
					count += 1
		return count


class Solution:

	def countSubstring(self, S):
		n = len(S)
		ans = 0
		for i in range(n):
			lower = 0
			upper = 0
			for j in range(i, n):
				if ord(S[j]) >= 65 and ord(S[j]) <= 90:
					upper += 1
				if ord(S[j]) >= 97 and ord(S[j]) <= 122:
					lower += 1
				if lower == upper:
					ans += 1
		return ans


class Solution:

	def countSubstring(self, S):
		c = 0
		A = [0] * len(S)
		for i in range(len(S)):
			(u, l) = (0, 0)
			if S[i].isupper():
				A[i] = 1
			else:
				A[i] = -1
		for i in range(1, len(S)):
			A[i] += A[i - 1]
		d = {}
		for i in range(len(S)):
			if A[i] == 0:
				c += 1
			if A[i] in d:
				c += d[A[i]]
				d[A[i]] += 1
			elif A[i] not in d:
				d[A[i]] = 1
		return c


class Solution:

	def countSubstring(self, S):
		c = 0
		for i in range(len(S) - 1):
			(u, l) = (0, 0)
			if S[i].isupper():
				u += 1
			else:
				l += 1
			for j in range(i + 1, len(S)):
				if S[j].islower():
					l += 1
				else:
					u += 1
				if u == l:
					c += 1
		return c


class Solution:

	def countSubstring(self, S):
		r = 0
		for i in range(0, len(S)):
			v = 0
			t = 0
			for j in range(i, len(S)):
				if S[j] >= 'a' and S[j] <= 'z':
					v = v + 1
				else:
					t = t + 1
				if v == t:
					r = r + 1
		return r


class Solution:

	def countSubstring(self, S):
		n = len(S)
		ans = 0
		for i in range(n):
			lower = 0
			upper = 0
			for j in range(i, n):
				if S[j].islower():
					lower += 1
				else:
					upper += 1
				if lower == upper:
					ans += 1
		return ans


class Solution:

	def countSubstring(self, S):
		x = 0
		p = len(S)
		c = 0
		for i in range(p - 1):
			j = i + 1
			u1 = 0
			l1 = 0
			if S[i].isupper():
				u1 = u1 + 1
			else:
				l1 = l1 + 1
			while j < p:
				if S[j].isupper():
					u1 = u1 + 1
				else:
					l1 = l1 + 1
				if u1 == l1:
					c = c + 1
				j = j + 1
		return c


class Solution:

	def countSubstring(self, S):
		ans = 0
		for x in range(len(S)):
			caps = 0
			smalls = 0
			for y in range(x, len(S)):
				if ord(S[y]) < 97:
					caps += 1
				else:
					smalls += 1
				if caps == smalls:
					ans += 1
		return ans


class Solution:

	def countSubstring(self, S):
		a = 0
		for i in range(len(S)):
			l = 0
			u = 0
			for j in range(i, len(S)):
				if ord(S[j]) >= 65 and ord(S[j]) <= 90:
					u += 1
				if ord(S[j]) >= 97 and ord(S[j]) <= 122:
					l += 1
				if l == u:
					a += 1
		return a


class Solution:

	def countSubstring(self, S):
		c = 0
		for i in range(len(S)):
			(up, low) = (0, 0)
			for j in range(i, len(S)):
				if S[j] >= 'A' and S[j] <= 'Z':
					up = up + 1
				elif S[j] >= 'a' and S[j] <= 'z':
					low = low + 1
				if up == low:
					c = c + 1
		return c


class Solution:

	def countSubstring(self, S):
		out = 0
		n = len(S)
		for x in range(n):
			cnt = 0
			sm = 0
			lg = 0
			for y in range(x, n):
				if ord(S[y]) <= ord('z') and ord(S[y]) >= ord('a'):
					sm += 1
				else:
					lg += 1
				if sm == lg:
					cnt += 1
			out += cnt
		return out


class Solution:

	def countSubstring(self, S):
		count = 0
		diff_counts = {0: 1}
		diff = 0
		for c in S:
			if c.islower():
				diff -= 1
			else:
				diff += 1
			count += diff_counts.get(diff, 0)
			diff_counts[diff] = diff_counts.get(diff, 0) + 1
		return count


class Solution:

	def countSubstring(self, S):
		count = 0
		n = len(S)
		for i in range(n):
			upper_count = 0
			lower_count = 0
			for j in range(i, n):
				if S[j].isupper():
					upper_count += 1
				else:
					lower_count += 1
				if upper_count == lower_count:
					count += 1
		return count


class Solution:

	def countSubstring(self, S):
		n = len(S)
		c = 0
		for i in range(n):
			f = 0
			for j in range(i, n):
				if S[j].islower():
					f -= 1
				else:
					f += 1
				if f == 0:
					c += 1
		return c


class Solution:

	def countSubstring(self, S):
		N = len(S)
		prevSum = {}
		res = 0
		currentSum = 0
		for i in range(N):
			if S[i] >= 'A' and S[i] <= 'Z':
				currentSum += 1
			else:
				currentSum -= 1
			if currentSum == 0:
				res += 1
			if currentSum in prevSum:
				res += prevSum[currentSum]
				prevSum[currentSum] += 1
			else:
				prevSum[currentSum] = 1
		return res


class Solution:

	def countSubstring(self, S):
		counter = {0: 1}
		summ = 0
		answer = 0
		for ch in S:
			case = 1 if ch.isupper() else -1
			summ += case
			if summ in counter:
				answer += counter[summ]
				counter[summ] += 1
			else:
				counter[summ] = 1
		return answer


class Solution:

	def countSubstring(self, S):
		output = 0
		n = len(S)
		for i in range(n - 1):
			count = 0
			for j in range(i, n):
				count += S[j].islower()
				count -= S[j].isupper()
				output += count == 0
		return output


class Solution:

	def countSubstring(self, S):
		cnt = 0
		for i in range(len(S)):
			lcnt = 0
			ucnt = 0
			for j in S[i:]:
				if j.islower():
					lcnt = lcnt + 1
				else:
					ucnt = ucnt + 1
				if lcnt == ucnt:
					cnt = cnt + 1
		return cnt


class Solution:

	def countSubstring(self, S):
		cnt = 0
		for i in range(len(S)):
			lCnt = 0
			uCnt = 0
			for j in range(i, len(S), 1):
				if S[j].islower():
					lCnt = lCnt + 1
				else:
					uCnt = uCnt + 1
				if lCnt == uCnt:
					cnt = cnt + 1
		return cnt


class Solution:

	def countSubstring(self, S):
		res = 0
		for i in range(len(S)):
			word = S[i]
			up = 0
			lw = 0
			if S[i].isupper():
				up += 1
			else:
				lw += 1
			for j in range(i + 1, len(S)):
				word += S[j]
				if S[j].isupper():
					up += 1
				else:
					lw += 1
				if up == lw:
					res += 1
		return res


class Solution:

	def countSubstring(self, S):
		pref = []
		sm = 0
		for c in S:
			if ord(c) < 97:
				sm += 1
			pref.append(sm)
		ans = 0
		for i in range(len(S)):
			for j in range(i + 1, len(S)):
				ln = j - i + 1
				cur = 0
				if i == 0:
					cur = pref[j]
				else:
					cur = pref[j] - pref[i - 1]
				if 2 * cur == ln:
					ans += 1
		return ans


class Solution:

	def countSubstring(self, S):
		r = 0
		for i in range(len(S)):
			a = c = 0
			for j in range(i, len(S)):
				if S[j].isupper():
					c += 1
				else:
					a += 1
				if a == c:
					r += 1
		return r


from collections import defaultdict

class Solution:

	def countSubstring(self, S):
		result = 0
		map = defaultdict(int)
		currsum = 0
		for i in S:
			if i.islower():
				currsum -= 1
			else:
				currsum += 1
			if currsum == 0:
				result += 1
			if currsum in map:
				result += map[currsum]
			map[currsum] += 1
		return result


class Solution:

	def countSubstring(self, S):
		prevsum = {}
		countsum = 0
		res = 0
		for i in range(len(S)):
			if (S[i] >= 'A') & (S[i] <= 'Z'):
				countsum += 1
			else:
				countsum -= 1
			if countsum == 0:
				res += 1
			if countsum in prevsum:
				res += prevsum[countsum]
			if countsum in prevsum:
				prevsum[countsum] += 1
			else:
				prevsum[countsum] = 1
		return res


class Solution:

	def countSubstring(self, S):
		cmap = {0: 1}
		s = 0
		ans = 0
		for x in S:
			if x.islower():
				alp = -1
			else:
				alp = 1
			s += alp
			if s in cmap:
				ans += cmap[s]
				cmap[s] += 1
			else:
				cmap[s] = 1
		return ans


class Solution:

	def countSubstring(self, s):
		n = len(s)
		count = 0
		for i in range(n):
			(low, high) = (0, 0)
			for j in range(i, n):
				if ord(s[j]) >= 65 and ord(s[j]) <= 90:
					low += 1
				else:
					high += 1
				if high == low:
					count += 1
		return count


class Solution:

	def countSubstring(self, S):
		c = 0
		res = 0
		b = 0
		for i in range(0, len(S)):
			for j in range(i, len(S)):
				if ord(S[j]) >= 65 and ord(S[j]) <= 90:
					c += 1
				else:
					b += 1
				if c == b:
					res += 1
			c = b = 0
		return res


class Solution:

	def countSubstring(self, S):
		c = 0
		(lc, uc) = (0, 0)
		for i in range(len(S)):
			if S[i].islower():
				lc += 1
			else:
				uc += 1
			for j in range(i + 1, len(S)):
				if S[j].islower():
					lc += 1
				else:
					uc += 1
				if lc == uc:
					c += 1
			(lc, uc) = (0, 0)
		return c


class Solution:

	def countSubstring(self, S):
		arr = [0]
		for i in S:
			if i.islower():
				arr.append(arr[-1] + 1)
			elif i.isupper():
				arr.append(arr[-1] - 1)
		cnt = 0
		for i in range(len(S)):
			for j in range(i + 1, len(S) + 1):
				if arr[j] - arr[i] == 0:
					cnt += 1
		return cnt


class Solution:

	def countSubstring(self, S):

		def up_or_low(char):
			if char.isupper():
				return 1
			return -1
		count = 0
		for i in range(len(S)):
			sum_status = 0
			temp_str = ''
			for w in S[i:]:
				sum_status += up_or_low(w)
				temp_str += w
				if sum_status == 0:
					count += 1
		return count


class Solution:

	def countSubstring(self, S):
		n = len(S)
		count = 0
		for i in range(n):
			(lc, uc) = (0, 0)
			start = i
			for j in range(start, n):
				if S[j].islower():
					lc += 1
				else:
					uc += 1
				if lc == uc:
					count += 1
		return count


class Solution:

	def countSubstring(self, S):
		output = list(S)
		count = 0
		for i in range(len(output)):
			l = u = 0
			for j in range(i, len(output)):
				if output[j].isupper():
					u += 1
				else:
					l += 1
				if l == u:
					count += 1
		return count


class Solution:

	def countSubstring(self, S):
		s = [1 if ch.isupper() else -1 for ch in S]
		mp = {0: 1}
		res = running_sum = 0
		for ele in s:
			running_sum += ele
			if running_sum in mp:
				res += mp[running_sum]
			mp[running_sum] = mp.get(running_sum, 0) + 1
		return res


class Solution:

	def countSubstring(self, S):
		total = 0
		for x in range(len(S)):
			lower = 0
			upper = 0
			p = S[x:]
			for t in range(len(p)):
				if p[t] >= 'a' and p[t] <= 'z':
					lower += 1
				else:
					upper += 1
				if lower == upper:
					total += 1
		return total


class Solution:

	def countSubstring(self, S):
		n = len(S)
		subs = 0
		for i in range(0, n):
			lower = upper = 0
			for j in range(i, n):
				if ord(S[j]) >= ord('a'):
					lower += 1
				else:
					upper += 1
				if lower == upper:
					subs += 1
		return subs


class Solution:

	def countSubstring(self, S):
		ans = 0
		for i in range(len(S)):
			sm1 = 0
			sm2 = 0
			for j in range(i, len(S), 1):
				if ord(S[j]) <= ord('z') and ord(S[j]) >= ord('a'):
					sm1 = sm1 + 1
				if ord(S[j]) <= ord('Z') and ord(S[j]) >= ord('A'):
					sm2 = sm2 + 1
				if sm1 == sm2:
					ans = ans + 1
		return ans