Given an array. Calculate the sum of lengths of contiguous subarrays having all distinct elements.
 
Example 1:
Input:
N=3
arr[] = { 1,2,3 }
Output: 10
Explanation: 
{1, 2, 3} is a subarray of length 3 with 
distinct elements. Total length of length
three = 3. {1, 2}, {2, 3} are 2 subarray 
of length 2 with distinct elements. Total 
length of lengths two = 2 + 2 = 4
{1}, {2}, {3} are 3 subarrays of length 1
with distinct element. Total lengths of 
length one = 1 + 1 + 1 = 3
Sum of lengths = 3 + 4 + 3 = 10
Example 2:
Input:
N=1
arr[] = { 1 }
Output: 1
Explanation: 
{1} is the only subarray with distinct 
elements of length 1.  
Your Task:
You don't need to read input or print anything. Your task is to complete the function sumoflength() that takes array arr and integer N as input parameters and returns the sum of lengths of contiguous subarrays having all distinct elements.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(N).
 
Constraints:
1 ≤ N ≤ 10^{6}

Source: geeksforgeeks | Difficulty: EASY
Tags: String algorithms

Data structures

Starter code: #User function Template for python3



class Solution:

    def sumoflength(self,arr,n):

      

Solutions:
class Solution:

	def sumoflength(self, arr, n):
		store = set()
		count = 0
		i = 0
		for item in arr:
			while i < n and (not arr[i] in store):
				store.add(arr[i])
				i += 1
			count += len(store) * (len(store) + 1) // 2
			store.remove(item)
		return count


class Solution:

	def sumoflength(self, arr, n):
		s = set()
		j = 0
		ans = 0
		for i in range(n):
			while j < n and arr[j] not in s:
				s.add(arr[j])
				j += 1
			ans += (j - i) * (j - i + 1) // 2
			s.remove(arr[i])
		return ans


class Solution:

	def sumoflength(self, arr, n):
		r = 0
		ans = 0
		set_ = set()
		for l in range(n):
			while r < n and arr[r] not in set_:
				set_.add(arr[r])
				r += 1
			ans += len(set_) * (len(set_) + 1) // 2
			set_.remove(arr[l])
		return ans


class Solution:

	def sumoflength(self, arr, n):

		def findsubs(arr, n):
			hm = {}
			dist_cnt = 0
			(start, end) = (0, 0)
			subs = 0
			length = 0
			while end < n:
				if arr[end] not in hm or hm[arr[end]] == 0:
					hm[arr[end]] = 1 + hm.get(arr[end], 0)
					subs += end - start + 1
					l = end - start + 1
					length += l * (l + 1) // 2
					end += 1
				else:
					hm[arr[start]] -= 1
					start += 1
			return length
		return findsubs(arr, n)


class Solution:

	def sumoflength(self, arr, n):
		hm = {}
		j = 0
		ans = 0
		for i in range(n):
			while j < n and arr[j] not in hm:
				hm[arr[j]] = True
				j += 1
			ans += (j - i) * (j - i + 1) // 2
			del hm[arr[i]]
		return ans


class Solution:

	def sumoflength(self, arr, n):
		counter = 0
		for i in range(n):
			h = {}
			for j in range(i, n):
				if arr[j] not in h:
					h[arr[j]] = 1
					counter += len(h)
				else:
					break
		return counter


class Solution:

	def sumoflength(self, arr, n):
		j = 0
		ans = 0
		l = []
		for i in range(n):
			while j < n and arr[j] not in l:
				l.append(arr[j])
				j += 1
			ans += (j - i) * (j - i + 1) // 2
			l.remove(arr[i])
		return ans


class Solution:

	def sumoflength(self, arr, n):
		setA = set()
		ans = 0
		count = 0
		for i in range(n):
			while count < n and arr[count] not in setA:
				setA.add(arr[count])
				count += 1
			ans += (count - i) * (count - i + 1) // 2
			setA.remove(arr[i])
		return ans


class Solution:

	def sumoflength(self, arr, n):
		ans = 0
		d = {}
		(left, right) = (0, 0)
		for (index, val) in enumerate(arr):
			if val in d:
				if d[val] < left:
					pass
				else:
					left = d[val] + 1
			p = index - left + 1
			ans += p * (p + 1) // 2
			d[val] = index
		return ans


from collections import defaultdict

class Solution:

	def sumoflength(self, arr, n):
		start = 0
		d = defaultdict(int)
		d[arr[0]] = 0
		ans = 1
		for i in range(1, n):
			if arr[i] not in d:
				d[arr[i]] = i
				l = i - start + 1
				ans += l * (l + 1) // 2
			elif arr[i] in d and d[arr[i]] < start:
				d[arr[i]] = i
				l = i - start + 1
				ans += l * (l + 1) // 2
			else:
				start = d[arr[i]] + 1
				d[arr[i]] = i
				l = i - start + 1
				ans += l * (l + 1) // 2
		return ans


class Solution:

	def sumoflength(self, arr, n):
		ans = 0
		left = right = 0
		chars = set()
		while left < n:
			while right < n and arr[right] not in chars:
				chars.add(arr[right])
				right += 1
			ans += (right - left) * (right - left + 1) // 2
			chars.remove(arr[left])
			left += 1
		return ans


class Solution:

	def sumoflength(self, arr, n):
		ans = release = 0
		memo = {}
		for acquire in range(n):
			currentVal = arr[acquire]
			memo[currentVal] = memo[currentVal] + 1 if currentVal in memo else 1
			while release <= acquire and memo[currentVal] > 1:
				disVal = arr[release]
				memo[disVal] -= 1
				release += 1
				if memo[disVal] == 0:
					del memo[disVal]
			length = acquire - release + 1
			ans += length * (length + 1) // 2
		return ans


class Solution:

	def sumoflength(self, arr, n):
		h = {}
		ans = 0
		left = 0
		for i in range(n):
			cc = arr[i]
			if cc in h:
				if h[cc] >= left:
					left = h[cc] + 1
				h[cc] = i
			else:
				h[cc] = i
			windowSize = i - left + 1
			length = windowSize * (windowSize + 1) // 2
			ans += length
		return ans