Given two arrays A and B of size N, the task is to find the maximum sum possible of a window in array B such that elements of the same window in array A are unique.
Example 1:
Input: N = 7
A = [0, 1, 2, 3, 0, 1, 4] 
B = [9, 8, 1, 2, 3, 4, 5] 
Output: 20
Explanation: The maximum sum possible 
in B[] such that all corresponding 
elements in A[] are unique is 
(9+8+1+2) = 20.
 
Example 2:
Input: N = 5
A = [0, 1, 2, 0, 2]
B = [5, 6, 7, 8, 2]
Output:  21
Ã¢â¬â¹Your Task:
This is a function problem. You don't need to take any input, as it is already accomplished by the driver code. You just need to complete the function returnMaxSum() that takes array A, array B, and integer N as parameters and returns the maximum possible sum.
 
Expected Time Complexity: O(N). 
Expected Auxiliary Space: O(N).
 
Constraints:
1 ≤ N ≤ 10^{5}

Source: geeksforgeeks | Difficulty: EASY
Tags: String algorithms

Data structures

Starter code: class Solution:

    def returnMaxSum(self, a, b, n):

        # Your code goes here

Solutions:
class Solution:

	def returnMaxSum(self, a, b, n):
		r = 0
		s = set()
		presum = [0] * (n + 1)
		presum[1] = b[0]
		for i in range(2, n + 1):
			presum[i] = presum[i - 1] + b[i - 1]
		m = 0
		for l in range(n):
			while r < n and a[r] not in s:
				s.add(a[r])
				r += 1
			m = max(m, presum[r] - presum[l])
			s.remove(a[l])
		return m


class Solution:

	def returnMaxSum(self, a, b, n):
		summa = 0
		maxi = 0
		setti = set()
		j = 0
		for i in range(n):
			while j < n and a[j] not in setti:
				setti.add(a[j])
				summa += b[j]
				j += 1
			maxi = max(maxi, summa)
			summa -= b[i]
			setti.remove(a[i])
		return maxi


from collections import defaultdict

class Solution:

	def returnMaxSum(self, a, b, n):
		left = 0
		maxsum = 0
		currsum = 0
		mp = defaultdict(int)
		for right in range(n):
			mp[a[right]] += 1
			currsum += b[right]
			if len(mp) < right - left + 1:
				while len(mp) < right - left + 1:
					currsum -= b[left]
					mp[a[left]] -= 1
					if mp[a[left]] == 0:
						del mp[a[left]]
					left += 1
			maxsum = max(maxsum, currsum)
		return maxsum


class Solution:

	def returnMaxSum(self, a, b, n):
		m = {}
		j = 0
		sums = 0
		maxi = 0
		for i in range(n):
			while a[i] in m:
				sums -= b[j]
				if m[a[j]] == 1:
					del m[a[j]]
				else:
					m[a[j]] -= 1
				j += 1
			m[a[i]] = 1
			sums += b[i]
			maxi = max(sums, maxi)
		return maxi


class Solution:

	def returnMaxSum(self, a, b, n):
		from collections import defaultdict
		hmap = defaultdict(int)
		hset = set()
		length = len(a)
		maxi = -int(1000000000.0) + 7
		(start, end) = (0, 0)
		ws = 0
		total = 0
		while end < length:
			total += b[end]
			hset.add(a[end])
			ws += 1
			while start < length and len(hset) < ws:
				total -= b[start]
				hset.remove(a[start])
				ws -= 1
				hset.add(a[end])
				start += 1
			if len(hset) == ws:
				maxi = max(maxi, total)
			end += 1
		return maxi


class Solution:

	def returnMaxSum(self, a, b, n):
		mp = set()
		result = 0
		cursum = 0
		curbegain = 0
		for i in range(0, n):
			while a[i] in mp:
				mp.remove(a[curbegain])
				cursum -= b[curbegain]
				curbegain += 1
			mp.add(a[i])
			cursum += b[i]
			result = max(result, cursum)
		return result


class Solution:

	def returnMaxSum(self, A, B, n):
		mp = set()
		result = 0
		curr_sum = curr_begin = 0
		for i in range(0, n):
			while A[i] in mp:
				mp.remove(A[curr_begin])
				curr_sum -= B[curr_begin]
				curr_begin += 1
			mp.add(A[i])
			curr_sum += B[i]
			result = max(result, curr_sum)
		return result


from collections import defaultdict
from math import inf

class Solution:

	def returnMaxSum(self, a, b, n):
		l = r = 0
		d = defaultdict(lambda : 0)
		msum = -inf
		wsum = 0
		while r < n:
			wsum += b[r]
			d[a[r]] += 1
			while l <= r and d[a[r]] > 1:
				wsum -= b[l]
				d[a[l]] -= 1
				l += 1
			msum = max(msum, wsum)
			r += 1
		return msum


class Solution:

	def returnMaxSum(self, a, b, n):
		d = {}
		low = 0
		high = 0
		curr_sum = 0
		max_sum = 0
		r = 0
		while high < len(a):
			while high < len(a) and a[high] not in d:
				d[a[high]] = 1
				curr_sum += b[high]
				high += 1
			max_sum = max(max_sum, curr_sum)
			while high < len(a) and a[high] in d:
				d[a[low]] -= 1
				curr_sum -= b[low]
				if d[a[low]] == 0:
					del d[a[low]]
				low += 1
			max_sum = max(max_sum, curr_sum)
		return max_sum


class Solution:

	def returnMaxSum(self, a, b, n):
		s = set()
		l = 0
		sum1 = 0
		ans = 0
		for r in range(n):
			sum1 += b[r]
			while a[r] in s and l <= r:
				sum1 -= b[l]
				s.remove(a[l])
				l += 1
			ans = max(ans, sum1)
			s.add(a[r])
		return ans


class Solution:

	def returnMaxSum(self, a, b, n):
		i = 0
		j = 0
		d = {}
		ans = 0
		r = 0
		while i < len(a):
			while i < len(a) and a[i] not in d:
				d[a[i]] = 1
				ans += b[i]
				i += 1
			r = max(ans, r)
			while i < len(a) and a[i] in d:
				d[a[j]] -= 1
				ans -= b[j]
				if d[a[j]] == 0:
					del d[a[j]]
				j += 1
			r = max(ans, r)
		return r


class Solution:

	def returnMaxSum(self, a, b, n):
		mp = set()
		result = 0
		curr_sum = curr_begin = 0
		for i in range(0, n):
			while a[i] in mp:
				mp.remove(a[curr_begin])
				curr_sum -= b[curr_begin]
				curr_begin += 1
			mp.add(a[i])
			curr_sum += b[i]
			result = max(result, curr_sum)
		return result


class Solution:

	def returnMaxSum(self, a, b, n):
		sm = [0] * (n + 1)
		for i in range(1, n + 1):
			sm[i] = sm[i - 1] + b[i - 1]
		d = {}
		s = 0
		d[a[0]] = 0
		e = 1
		mx = sm[1]
		while e < n:
			if a[e] in d:
				s = max(s, d[a[e]] + 1)
			d[a[e]] = e
			mx = max(mx, sm[e + 1] - sm[s])
			e += 1
		return mx


class Solution:

	def returnMaxSum(self, a, b, n):
		k = 0
		t = 0
		l = [a[0]]
		ans = 0
		for i in range(1, n):
			if a[i] not in l[k:]:
				l.append(a[i])
			else:
				t = sum(b[k:i])
				if t > ans:
					ans = t
				x = l[k:].index(a[i])
				k += x + 1
				l.append(a[i])
		if sum(b[k:]) > ans:
			ans = sum(b[k:])
		return ans


class Solution:

	def returnMaxSum(self, a, b, n):
		ans_ = 0
		d = set()
		j = 0
		res = 0
		for i in range(n):
			while a[i] in d:
				d.remove(a[j])
				ans_ -= b[j]
				j += 1
			if a[i] not in d:
				d.add(a[i])
				ans_ += b[i]
			res = max(res, ans_)
		return res
		result = max(result, curr_sum)