Given a string w, integer array b,  character array x and an integer n. n is the size of array b and array x. Find a substring which has the sum of the ASCII values of its every character, as maximum. ASCII values of some characters are redefined.
Note: Uppercase & lowercase both will be present in the string w. Array b and Array x contain corresponding redefined ASCII values. For each i, b[i] contain redefined ASCII value of character x[i].
Example 1:
Input:
W = abcde
N = 1
X[] = { 'c' }
B[] = { -1000 }
Output:
de
Explanation:
Substring "de" has the
maximum sum of ascii value,
including c decreases the sum value
Example 2:
Input:
W = dbfbsdbf 
N = 2
X[] = { 'b','s' }
B[] = { -100, 45  }
Output:
dbfbsdbf
Explanation:
Substring "dbfbsdbf" has the maximum
sum of ascii value.
Your Task:
You don't need to read input or print anything. Your task is to complete the function maxSum() which takes string W, character array X, integer array B, integer N as length of array X and B as input parameters and returns the substring with the maximum sum of ascii value.
 
Expected Time Complexity: O(|W|)
Expected Auxiliary Space: O(1)
Constraints:
1<=|W|<=100000
1<=|X|<=52
-1000<=B_{i}<=1000
Each character of W and A will be from a-z, A-Z.

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Dynamic programming

Starter code: #User function Template for python3





class Solution:

    def maxSum (self, w, x, b, n):

        #code here

Solutions:
import sys

class Solution:

	def maxSum(self, w, x, b, n):
		max_so_far = -sys.maxsize
		max_current = 0
		i = 0
		j = 0
		s = 0
		if n == 0:
			return w
		for cur in range(len(w)):
			new_asc = ord(w[cur])
			if w[cur] in x:
				new_asc = b[x.index(w[cur])]
			max_current += new_asc
			if max_so_far < max_current:
				max_so_far = max_current
				i = s
				j = cur
			if max_current < 0:
				max_current = 0
				s = cur + 1
		return w[i:j + 1]


class Solution:

	def __init__(self):
		self.mp = dict()

	def asc(self, letr):
		if self.mp.get(letr) == None:
			return ord(letr)
		return self.mp[letr]

	def maxSum(self, w, x, b, n):
		self.mp.clear()
		for i in range(n):
			self.mp[x[i]] = b[i]
		curr_sum = self.asc(w[0])
		max_sum = self.asc(w[0])
		left_max = 0
		right_max = 0
		left = 0
		right = 0
		for i in range(1, len(w)):
			letr = w[i]
			val = self.asc(w[i])
			if curr_sum + val <= val:
				curr_sum = val
				left = i
				right = i
			else:
				curr_sum += val
				right = i
			if max_sum < curr_sum:
				max_sum = curr_sum
				left_max = left
				right_max = right
		return w[left_max:right_max + 1]


class Solution:

	def maxSum(self, w, x, b, n):
		d = dict(zip(x, b))
		size = len(w)
		maxi = -1000000000.0
		cur = 0
		curStr = ''
		ans = ''
		for i in range(size):
			if w[i] in d.keys():
				cur += d[w[i]]
			else:
				cur += ord(w[i])
			curStr += w[i]
			if maxi < cur:
				maxi = cur
				ans = curStr
			if cur < 0:
				cur = 0
				curStr = ''
		return ans


class Solution:

	def maxSum(self, w, x, b, n):
		for i in range(n):
			h = dict(zip(x, b))
			s = 0
			t = ''
			ans = ''
			mx = -1000000000.0
			a = 0
		for i in range(len(w)):
			if w[i] in h:
				a = h[w[i]]
			else:
				a = ord(w[i])
			s += a
			t += w[i]
			if s > mx:
				mx = s
				ans = t
			if s < 0:
				s = 0
				t = ''
		return ans


class Solution:

	def maxSum(self, w, x, b, n):
		asc = {}
		for i in range(n):
			asc[x[i]] = b[i]
		res = [[0, 1], self.asc_value(w[0], asc)]
		cur = [[0, 1], self.asc_value(w[0], asc)]
		for i in range(1, len(w)):
			ch = w[i]
			val = self.asc_value(ch, asc)
			if cur[1] + val < val:
				cur = [[i, i + 1], val]
			elif cur[1] + val > 0:
				cur[0][1] = i + 1
				cur[1] += val
			else:
				cur = [[i, i + 1], val]
			if res[1] <= cur[1]:
				res = [[cur[0][0], cur[0][1]], cur[1]]
		return w[res[0][0]:res[0][1]]

	def asc_value(self, ch, asc):
		if ch in asc:
			return asc[ch]
		asc[ch] = ord(ch)
		return asc[ch]


class Solution:

	def maxSum(self, w, x, b, n):
		W = [b[x.index(i)] if i in x else ord(i) for i in w]
		(max_global, max_current) = (float('-inf'), 0)
		(start, end, s) = (0, 0, 0)
		for i in range(len(W)):
			max_current += W[i]
			if max_global < max_current:
				max_global = max_current
				start = s
				end = i
			if max_current < 0:
				max_current = 0
				s = i + 1
		return w[start:end + 1]


class Solution:

	def maxSum(self, w, x, b, n):
		all_negative = 1
		max_position = -1
		max_value = -1000000
		for i in range(0, len(w)):
			if w[i] in x:
				check = b[x.index(w[i])]
			else:
				check = ord(w[i])
			if check > 0:
				all_negative = 0
				break
			if check > max_value:
				max_value = check
				max_position = i
		if all_negative == 1:
			return w[max_position]
		cs = 0
		ms = 0
		l = -1
		result = ''
		for i in range(0, len(w)):
			if w[i] in x:
				cs = cs + b[x.index(w[i])]
			else:
				cs = cs + ord(w[i])
			if cs < 0:
				cs = 0
				l = i
			if cs > ms:
				result = w[l + 1:i + 1]
				ms = cs
		return result


class Solution:

	def maxSum(self, W, X, B, n):
		cs = 0
		ms = -1000000000
		res = ''
		start = end = s = 0
		if len(W) == 1:
			res = W
			return res
		for i in range(len(W)):
			if W[i] in X:
				ind = X.index(W[i])
				x = B[ind]
			else:
				x = ord(W[i])
			cs += x
			if cs > ms:
				ms = cs
				start = s
				end = i
			if cs < 0:
				cs = 0
				s = i + 1
		for i in range(start, end + 1):
			res += W[i]
		return res


class Solution:

	def maxSum(self, w, x, b, n):
		s = 0
		cs = -float('inf')
		ss = ''
		css = ''
		for c in w:
			if c in x:
				i = x.index(c)
				s += b[i]
				ss = ss + x[i]
			else:
				s += ord(c)
				ss = ss + c
			if cs < s:
				cs = s
				css = ss
			if s < 0:
				s = 0
				ss = ''
		return css


class Solution:

	def maxSum(self, w, x, b, n):
		mp = {}
		for i in range(n):
			mp[x[i]] = b[i]
		asciiList = []
		for i in w:
			if i in mp.keys():
				asciiList.append(mp[i])
			else:
				asciiList.append(ord(i))
		ans = ''
		max_sum = int(-1000000000.0)
		local_sum = 0
		local_ans = ''
		for i in range(len(w)):
			if asciiList[i] > local_sum + asciiList[i]:
				local_ans = w[i]
				local_sum = asciiList[i]
			else:
				local_ans += w[i]
				local_sum += asciiList[i]
			if local_sum > max_sum:
				ans = local_ans
				max_sum = local_sum
		return ans


class Solution:

	def maxSum(self, w, x, b, n):
		max_so_far = -10000000
		max_ending_here = 0
		s = ''
		for i in w:
			if i in x:
				c = x.index(i)
				max_ending_here += b[c]
				s += i
			else:
				max_ending_here += ord(i)
				s += i
			if max_so_far < max_ending_here:
				max_so_far = max_ending_here
				t = ''
			elif t == '':
				t = s[:-1]
			if max_ending_here < 0:
				max_ending_here = 0
				s = ''
		if max_so_far > max_ending_here:
			return t
		elif max_so_far < 0:
			return w
		else:
			return s


import sys

class Solution:

	def maxSum(self, w, x, b, n):

		def getASCII(c):
			if w[i] in x:
				return b[x.index(w[i])]
			else:
				return ord(w[i])
		sum = 0
		max_sum = ord(w[0])
		start = 0
		cur = 0
		end = 0
		for i in range(len(w)):
			sum += getASCII(w[i])
			if sum > max_sum:
				start = cur
				end = i
				max_sum = sum
			if sum < 0:
				sum = 0
				cur = i + 1
		ans = []
		for i in range(start, end + 1):
			ans.append(w[i])
		return ''.join(ans)


class Solution:

	def maxSum(self, w, x, b, n):
		csum = 0
		msf = 0
		dic = {}
		for ch in w:
			dic[ch] = ord(ch)
		for i in range(0, len(x)):
			dic[x[i]] = b[i]
		i = 0
		start = 0
		end = 0
		s = 0
		while i < len(w):
			if csum >= 0:
				csum += dic[w[i]]
			else:
				csum = dic[w[i]]
				s = i
			if msf < csum:
				msf = csum
				start = s
				end = i
			i += 1
		return w[start:end + 1]


class Solution:

	def maxSum(self, w, x, b, n):
		res = -float('infinity')
		resString = ''
		tempStrig = ''
		sum = 0
		mydict = dict()
		for i in range(len(x)):
			mydict[x[i]] = b[i]
		for i in w:
			val = mydict[i] if i in mydict else ord(i)
			sum += val
			tempStrig += i
			if sum > res:
				res = sum
				resString = tempStrig
			if sum < 0:
				tempStrig = ''
				sum = 0
		return resString


from sys import maxsize

class Solution:

	def maxSum(self, w, x, b, n):
		a_w = []
		for i in range(len(w)):
			d = zip(x, b)
			d = dict(d)
			if w[i] in d:
				a_w.append(d[w[i]])
			else:
				a_w.append(ord(w[i]))
		summ = 0
		start = 0
		end = 0
		max_sum = -maxsize
		l = 0
		for i in range(len(a_w)):
			summ = summ + a_w[i]
			if summ > max_sum:
				max_sum = summ
				start = l
				end = i
			if summ < 0:
				summ = 0
				l = i + 1
		return w[start:end + 1]


class Solution:

	def maxSum(self, w, x, b, n):
		map = {}
		char = 'a'
		while char <= 'z':
			map[char] = ord(char)
			char = chr(ord(char) + 1)
		char = 'A'
		while char <= 'Z':
			map[char] = ord(char)
			char = chr(ord(char) + 1)
		for i in range(n):
			map[x[i]] = b[i]
		(res, sum, str, start) = (map[w[0]], 0, w[0], 0)
		for i in range(len(w)):
			x = w[i]
			sum += map[x]
			if res < sum:
				res = sum
				str = w[start:i + 1]
			if sum < 0:
				(sum, start) = (0, i + 1)
		return str


class Solution:

	def maxSum(self, w, x, b, n):
		d = {}
		m = ''
		min = -1001
		for i in range(0, n):
			d[x[i]] = b[i]
			if b[i] > min:
				min = b[i]
				m = '' + x[i]
			else:
				continue
		for i in range(0, len(w)):
			if d.get(w[i], 1001) == 1001:
				d[w[i]] = ord(w[i])
			else:
				continue
		p = min
		t = 0
		c = m
		s = ''
		for i in range(0, len(w)):
			if t + d[w[i]] > 0 and t + d[w[i]] > p:
				s = s + w[i]
				c = '' + s
				t = t + d[w[i]]
				p = 0 + t
			elif t + d[w[i]] > 0:
				s = s + w[i]
				t = t + d[w[i]]
			else:
				t = 0
				s = ''
		return c


class Solution:

	def maxSum(self, w, x, b, n):
		max = -9999
		sum = 0
		asc = 0
		z = ''
		ans = ''
		v = {}
		for (i, j) in zip(x, b):
			v[i] = j
		for i in range(len(w)):
			if w[i] in v:
				asc = v[w[i]]
			else:
				asc = ord(w[i])
			sum = sum + asc
			z = z + w[i]
			if sum > max:
				max = sum
				ans = z
			if sum < 0:
				sum = 0
				z = ''
		return ans


class Solution:

	def fillasciivalue(self, x, b, n, lower, upper):
		for i in range(n):
			value = ord(x[i])
			if value >= 65 and value <= 90:
				upper[value - 65] = b[i]
			else:
				lower[value - 97] = b[i]

	def maxSum(self, w, x, b, n):
		lower = [i for i in range(97, 123)]
		upper = [i for i in range(65, 91)]
		self.fillasciivalue(x, b, n, lower, upper)
		maxvalue = 0
		max_till_now = 0
		ans = ''
		tmp = ''
		least_negative_chr = ''
		negative = -10 ** 9
		for alpha in w:
			value = ord(alpha)
			sm = upper[value - 65] if value >= 65 and value <= 90 else lower[value - 97]
			maxvalue += sm
			tmp += alpha
			if maxvalue < 0:
				maxvalue = 0
				tmp = ''
			if sm < 0 and sm > negative:
				negative = sm
				least_negative_chr = alpha
			if max_till_now < maxvalue:
				ans = tmp
				max_till_now = maxvalue
		return ans if ans != '' else least_negative_chr


class Solution:

	def maxSum(self, w, x, b, n):
		dp = {}
		for i in range(n):
			dp[x[i]] = b[i]
		sum = 0
		maxStart = 0
		maxEnd = 0
		start = 0
		end = 0
		if dp.get(w[0]) == None:
			maxSum = ord(w[0])
		else:
			maxSum = dp[w[0]]
		for i in w:
			if dp.get(w[end]) == None:
				sum += ord(w[end])
			else:
				sum += dp[w[end]]
			if sum > maxSum:
				maxSum = sum
				maxStart = start
				maxEnd = end
			if sum < 0:
				start = end + 1
				end = end
				sum = 0
			end += 1
		return w[maxStart:maxEnd + 1]


class Solution:

	def maxSum(self, w, x, b, n):
		char_dict = {}
		for (ch, val) in zip(x, b):
			char_dict[ch] = val
		(total, max_total) = (0, float('-inf'))
		l = 0
		res = ''
		for i in range(len(w)):
			if w[i] in char_dict:
				total += char_dict[w[i]]
			else:
				total += ord(w[i])
			if max_total < total:
				max_total = total
				res = w[l:i + 1]
			if total < 0:
				total = 0
				l = i + 1
		return res


class Solution:

	def maxSum(self, w, x, b, n):
		asc = {}
		for i in range(len(w)):
			asc[w[i]] = ord(w[i])
		for i in range(n):
			asc[x[i]] = b[i]
		maxsum = currsum = 0
		maxres = res = ''
		for i in range(len(w)):
			if currsum + asc[w[i]] >= 0:
				currsum += asc[w[i]]
				res += w[i]
			else:
				currsum = 0
				res = ''
			if currsum > maxsum:
				maxsum = currsum
				maxres = res
		if maxres == '':
			maxres = w[0]
			for i in range(1, len(w)):
				if asc[maxres] < asc[w[i]]:
					maxres = w[i]
		return maxres


class Solution:

	def maxSum(self, w, x, b, n):
		val = []
		for i in w:
			if i not in x:
				val.append(ord(i))
			else:
				val.append(b[x.index(i)])
		maxyet = 0
		maxcur = 0
		start = 0
		s = 0
		e = 0
		for i in range(len(val)):
			maxcur = maxcur + val[i]
			if maxcur > maxyet:
				maxyet = maxcur
				start = s
				e = i
			elif maxcur < 0:
				maxcur = 0
				s = i + 1
		return w[start:e + 1]


class Solution:

	def maxSum(self, w, x, b, n):
		ms = -999999999999999999 - 1
		l = 0
		res = ''
		pres = ''
		me = 0
		for i in w[:]:
			if i in x:
				l = b[x.index(i)]
			else:
				l = ord(i)
			me += l
			res += i
			if ms < me:
				ms = me
				pres = res
			if me < 0:
				me = 0
				res = ''
		return pres


import copy
from sys import maxsize

class Solution:

	def maxSum(self, w, x, b, n):
		wl = [i for i in w]
		wa = [ord(i) for i in wl]
		wd = dict(list(zip(wl, wa)))
		xb = dict(list(zip(x, b)))
		wdu = copy.deepcopy(wd)
		wdu.update(xb)
		nwa = [wdu[i] for i in wl]
		(s, e) = self.max_sum(nwa)
		return w[s:e + 1]

	def max_sum(self, arr):
		msf = -maxsize - 1
		meh = 0
		start = 0
		end = 0
		s = 0
		for i in range(len(arr)):
			meh = meh + arr[i]
			if meh > msf:
				msf = meh
				end = i
				start = s
			if meh < 0:
				meh = 0
				s = i + 1
		return (start, end)


import math

class Solution:

	def maxSum(self, w, x, b, n):
		maxSoFar = maxEndingHere = 0
		start = end = s = 0
		dic = {}
		for i in range(n):
			dic[x[i]] = b[i]
		for i in range(len(w)):
			if w[i] in dic:
				maxEndingHere += dic[w[i]]
			else:
				maxEndingHere += ord(w[i])
			if maxEndingHere > maxSoFar:
				maxSoFar = maxEndingHere
				start = s
				end = i
			if maxEndingHere < 0:
				maxEndingHere = 0
				s = i + 1
		return w[start:end + 1]


class Solution:

	def maxSum(self, w, x, b, n):
		dic = dict(zip(x, b))
		currsum = globalSum = 0
		start = end = s = 0
		for i in range(len(w)):
			k = ord(w[i])
			if dic.get(w[i]) is None:
				currsum += k
			else:
				currsum += dic[w[i]]
			if currsum > globalSum:
				globalSum = currsum
				start = s
				end = i
			if currsum < 0:
				currsum = 0
				s = i + 1
		return w[start:end + 1]


class Solution:

	def maxSum(self, w, x, b, n):
		s = 0
		e = 0
		ans = ''
		l = []
		start = s
		sum = 0
		max = -1
		for ele in w:
			if ele in x:
				l.append(b[x.index(ele)])
			else:
				l.append(ord(ele))
		for i in range(len(w)):
			sum = sum + l[i]
			if sum > max:
				max = sum
				start = s
				e = i
			if sum < 0:
				sum = 0
				s = i + 1
		for j in range(start, e + 1):
			ans = ans + w[j]
		return ans


class Solution:

	def maxSum(self, w, x, b, n):
		maxx = float('-inf')
		val = 0
		new_str = ''
		start = 0
		dic = {}
		for (i, (x_, b_)) in enumerate(zip(x, b)):
			dic[x_] = b_
		for (i, c) in enumerate(w):
			if c in dic:
				val = val + dic[c]
			else:
				val = val + ord(c)
			if val > maxx:
				maxx = val
				new_str = w[start:i + 1]
			if val < 0:
				val = 0
				start = i + 1
		return new_str


from sys import maxsize

class Solution:

	def maxSum(self, w, x, b, n):
		ans_str = ''
		ans_ascii = -maxsize - 1
		curr = 0
		curr_str = ''
		w = list(w)
		for i in range(len(w)):
			curr_str += w[i]
			if w[i] in x:
				for j in range(n):
					if x[j] == w[i]:
						curr += b[j]
			else:
				curr += ord(w[i])
			if ans_ascii < curr:
				ans_ascii = curr
				ans_str = curr_str
			if curr < 0:
				curr = 0
				curr_str = ''
		return ans_str


class Solution:

	def maxSum(self, w, x, b, n):
		if len(w) == 1:
			return w
		arr = {}
		for i in w:
			if i in x:
				arr[i] = b[x.index(i)]
			else:
				arr[i] = ord(i)
		max_so_far = 0
		max_end = 0
		s = 0
		end = 0
		for i in range(len(w)):
			max_end += arr[w[i]]
			if max_end > max_so_far:
				max_so_far = max_end
				start = s
				end = i
			if max_end < 0:
				max_end = 0
				s = i + 1
		return w[start:end + 1]


import sys

class Solution:

	def maxSum(self, w, x, b, n):
		curr_sum = 0
		max_sum = ~sys.maxsize
		m = {}
		res = ''
		curr_substr = ''
		for i in range(n):
			m[x[i]] = b[i]
		for i in range(len(w)):
			if w[i] not in m:
				curr_sum += ord(w[i])
			else:
				curr_sum += m[w[i]]
			curr_substr += w[i]
			if curr_sum > max_sum:
				max_sum = curr_sum
				res = curr_substr
			if curr_sum < 0:
				curr_sum = 0
				curr_substr = ''
		return res


class Solution:

	def maxSum(self, w, x, b, n):
		s = ''
		dict = {a: b for (a, b) in zip(x, b)}
		(max_ending_here, max_so_far) = (-float('inf'), -float('inf'))
		(curr, res) = ('', '')
		for i in w:
			val = dict[i] if i in dict else ord(i)
			if max_ending_here < 0:
				curr = i
				max_ending_here = val
			else:
				max_ending_here += val
				curr += i
			if max_ending_here > max_so_far:
				max_so_far = max_ending_here
				res = curr
		return res


class Solution:

	def maxSum(self, w, x, b, n):
		d = {}
		str = ''
		sum = 0
		max = -999999
		for (i, j) in zip(x, b):
			d[i] = j
		for i in w:
			str = str + i
			if i in d:
				sum = sum + d[i]
			else:
				sum = sum + ord(i)
			if sum > max:
				max = sum
				res = str
			if sum < 0:
				sum = 0
				str = ''
		return res


class Solution:

	def maxSum(self, w, x, b, n):
		dic = {}
		for i in range(n):
			dic[x[i]] = b[i]
		ans = 0
		s = ''
		fin = -999
		fin_str = ''
		for i in w:
			if i not in dic:
				s += i
				ans += ord(i)
			else:
				s += i
				ans += dic[i]
			if ans > fin:
				fin = ans
				fin_str = s
			if ans < 0:
				ans = 0
				s = ''
		return fin_str


class Solution:

	def maxSum(self, s, chars, values, n):
		d = {char: val for (char, val) in zip(chars, values)}
		curr = 0
		ans = float('-inf')
		curr_str = ''
		ans_str = ''
		for i in s:
			curr_str += i
			if i in d:
				curr += d[i]
			else:
				curr += ord(i)
			if curr > ans:
				ans = max(ans, curr)
				ans_str = curr_str
			if curr < 0:
				curr = 0
				curr_str = ''
		return ans_str


from sys import maxsize

class Solution:

	def maxSum(self, w, x, b, n):
		ts = 0
		strt = 0
		end = 0
		max = -maxsize - 1
		sum = 0
		for i in range(0, len(w)):
			if w[i] in x:
				sum = sum + b[x.index(w[i])]
			else:
				sum = sum + ord(w[i])
			if max < sum:
				max = sum
				strt = ts
				end = i
			if sum < 0:
				sum = 0
				ts = i + 1
		return w[strt:end + 1]


class Solution:

	def maxSum(self, w, x, b, n):
		if len(w) <= 1:
			return w
		dic = {}
		max_till_now = 0
		max_so_far = -99999999999999999
		ans = ''
		ans2 = ''
		for i in range(len(w)):
			if w[i] in x:
				index = x.index(w[i])
				max_till_now = max_till_now + b[index]
			else:
				max_till_now = max_till_now + ord(w[i])
			ans += w[i]
			if max_so_far < max_till_now:
				max_so_far = max_till_now
				ans2 = ans
			if max_till_now < 0:
				max_till_now = 0
				ans = ''
		return ans2


class Solution:

	def maxSum(self, w, x, b, n):
		A = []
		if len(w) == 1:
			return w
		mp = {}
		for i in range(n):
			mp[x[i]] = b[i]
		curr_sum = 0
		max_sum = -100000
		curr_s = ''
		max_s = ''
		for i in range(len(w)):
			if w[i] in mp:
				x = mp[w[i]]
			else:
				x = ord(w[i])
			curr_sum = curr_sum + x
			if curr_sum < 0:
				curr_sum = 0
				curr_s = ''
			else:
				curr_s = curr_s + w[i]
			if max_sum < curr_sum:
				max_sum = curr_sum
				max_s = curr_s
		return max_s


import sys

class Solution:

	def maxSum(self, w, x, b, n):
		res = []
		for i in w:
			if i in x:
				res.append(b[x.index(i)])
			else:
				res.append(ord(i))
		maxsum = -1 * sys.maxsize
		f = 0
		l = 0
		c = 0
		p = [0, 0]
		for i in range(len(res)):
			c += res[i]
			if maxsum < c:
				maxsum = c
				p[:] = [f, i]
			if c < 0:
				c = 0
				f = i + 1
		res = ''
		for i in range(p[0], p[1] + 1):
			res = res + w[i]
		return res


from sys import maxsize

class Solution:

	def maxSum(self, w, x, b, n):
		asci = [b[x.index(i)] if i in x else ord(i) for i in w]
		maxf = -maxsize - 1
		maxe = start = end = s = 0
		for i in range(len(asci)):
			maxe += asci[i]
			if maxf < maxe:
				maxf = maxe
				start = s
				end = i
			if maxe < 0:
				maxe = 0
				s = i + 1
		return w[start:end + 1]


class Solution:

	def maxSum(self, w, x, b, n):
		d = dict()
		n = len(w)
		for i in range(ord('A'), ord('Z') + 1):
			d[chr(i)] = i
		for i in range(ord('a'), ord('z') + 1):
			d[chr(i)] = i
		for (i, j) in zip(x, b):
			d[i] = j
		anss = -1
		an = -99999999
		anse = -1
		curs = -1
		cure = -1
		cu = 0
		for i in range(n):
			cu += d[w[i]]
			if curs == -1:
				curs = i
				cure = i
			else:
				cure = i
			if cu > an:
				anss = curs
				anse = cure
				an = cu
			if cu < 0:
				cu = 0
				curs = -1
				cure = -1
		return w[anss:anse + 1]


class Solution:

	def maxSum(self, w, x, b, n):
		(start, stop, s) = (0, 0, 0)
		su = 0
		res = 0
		for i in range(len(w)):
			if w[i] not in x:
				su += ord(w[i])
			else:
				su += b[x.index(w[i])]
			if su < 0:
				su = 0
				s = i + 1
			if res < su:
				res = su
				start = s
				stop = i
		return w[start:stop + 1]


class Solution:

	def maxSum(self, w, x, b, n):
		sum_val = 0
		max_val = ord(w[0])
		max_string = w[0]
		my_dict = {}
		for _ in range(len(x)):
			my_dict[x[_]] = b[_]
		final_string = w[0]
		counter = 0
		for _ in w:
			if counter != 0:
				max_string += _
			if _ in my_dict.keys():
				sum_val += my_dict[_]
			else:
				sum_val += ord(_)
			if max_val <= sum_val:
				final_string = max_string
			max_val = max(max_val, sum_val)
			if sum_val < 0:
				sum_val = 0
				max_string = ''
			counter = 1
		return final_string


class Solution:

	def maxSum(self, w, x, b, n):

		def solve(a, size):
			max_so_far = float('-inf') - 1
			max_ending_here = 0
			start = 0
			end = 0
			s = 0
			for i in range(0, size):
				max_ending_here += a[i]
				if max_so_far < max_ending_here:
					max_so_far = max_ending_here
					start = s
					end = i
				if max_ending_here < 0:
					max_ending_here = 0
					s = i + 1
			return (start, end)
		arr = []
		for i in w:
			if i not in x:
				arr.append(ord(i))
			else:
				arr.append(b[x.index(i)])
		(s, e) = solve(arr, len(arr))
		return w[s:e + 1]


class Solution:

	def maxSum(self, w, x, b, n):
		ump = {}
		for i in range(n):
			ump[x[i]] = b[i]
		(start, stop, s) = (0, 0, 0)
		(res, sum) = (0, 0)
		for i in range(len(w)):
			if w[i] in ump:
				sum += ump[w[i]]
			else:
				sum += ord(w[i])
			if sum < 0:
				sum = 0
				s = i + 1
			if sum > res:
				res = sum
				start = s
				stop = i
		return w[start:stop + 1]


class Solution:

	def maxSum(self, w, x, b, n):
		max_s = 0
		maxsum = -10000
		d = {}
		(s, start, stop) = (0, 0, 0)
		for i in range(n):
			d[x[i]] = b[i]
		for i in range(len(w)):
			if w[i] in d:
				max_s += d[w[i]]
			else:
				max_s += ord(w[i])
			if max_s > maxsum:
				maxsum = max_s
				start = s
				stop = i
			if max_s < 0:
				max_s = 0
				s = i + 1
		return w[start:stop + 1]


class Solution:

	def maxSum(self, w, x, b, n):
		arr = [b[x.index(i)] if i in x else ord(i) for i in w]
		max1 = -9999
		ends = 0
		sub1 = ''
		sub2 = ''
		for i in range(len(w)):
			ends += arr[i]
			sub1 += w[i]
			if ends > max1:
				max1 = ends
				sub2 = sub1
			if ends < 0:
				ends = 0
				sub1 = ''
		return sub2


class Solution:

	def maxSum(self, w, x, b, n):
		re = {}
		for i in range(n):
			re[x[i]] = b[i]
		arr = []
		for i in range(len(w)):
			if w[i] in re:
				arr.append(re[w[i]])
			else:
				arr.append(ord(w[i]))
		pos = 0
		maxi = -10 ** 9
		s = 0
		prev = 0
		st = ''
		ans = ''
		for i in range(len(arr)):
			s += arr[i]
			st += w[i]
			if arr[i] > s:
				st = w[i]
				s = arr[i]
			if s > maxi:
				maxi = s
				ans = st
		return ans


from sys import maxsize

class Solution:

	def maxSum(self, w, x, b, n):
		weight = []
		for i in range(len(w)):
			value = ord(w[i])
			if w[i] in x:
				index = x.index(w[i])
				value = b[index]
			weight.append(value)
		max_so_far = -maxsize - 1
		max_ending_here = 0
		start = 0
		end = 0
		s = 0
		for i in range(0, len(weight)):
			max_ending_here += weight[i]
			if max_so_far < max_ending_here:
				max_so_far = max_ending_here
				start = s
				end = i
			if max_ending_here < 0:
				max_ending_here = 0
				s = i + 1
		return w[start:end + 1]


from sys import maxsize

class Solution:

	def maxSum(self, w, x, b, n):
		dict = {}
		for ele in w:
			if ele not in dict:
				dict[ele] = ord(ele)
		for i in range(len(x)):
			if x[i] in dict:
				dict[x[i]] = b[i]
		start = 0
		end = 0
		max_sum = 0
		cur_sum = 0
		s = 0
		i = 0
		for i in range(len(w)):
			cur_sum += dict[w[i]]
			if cur_sum < 0:
				cur_sum = 0
				s = i + 1
			if max_sum < cur_sum:
				max_sum = cur_sum
				start = s
				end = i
		return w[start:end + 1]


class Solution:

	def maxSum(self, w, x, b, n):
		c = {i: j for (i, j) in zip(x, b)}
		t = 0
		m = -10 ** 9
		s = ''
		ts = ''
		for i in w:
			ts += i
			if i in c:
				t += c[i]
			else:
				t += ord(i)
			if m < t:
				s = ts
				m = t
			if t < 0:
				t = 0
				ts = ''
		return s


class Solution:

	def maxSum(self, w, x, b, n):
		asci = {}
		for i in 'qwertyuiopasdfghjklzxcvbnmQWERTYUIOPASDFGHJKLZXCVBNM':
			asci[i] = ord(i)
		for i in range(n):
			asci[x[i]] = b[i]
		arr = []
		for i in w:
			arr.append(asci[i])
		i = 0
		j = 0
		sm = 0
		ans = -10000
		ansi = 0
		ansj = 0
		while i < len(w):
			sm += arr[i]
			if sm > ans:
				ans = sm
				ansi = i
				ansj = j
			if sm < 0:
				sm = 0
				j = i + 1
			i += 1
		return w[ansj:ansi + 1]


class Solution:

	def maxSum(self, w, x, b, n):
		sumSoFar = 0
		strSoFar = ''
		maxSum = -100000000
		lookup = {x[i]: b[i] for i in range(n)}
		res = ''
		for ch in w:
			if ch in lookup:
				v = lookup[ch]
			else:
				v = ord(ch)
			sumSoFar += v
			strSoFar += ch
			if sumSoFar > maxSum:
				maxSum = sumSoFar
				res = strSoFar
			if sumSoFar < 0:
				sumSoFar = 0
				strSoFar = ''
		return res


class Solution:

	def maxSum(self, w, x, b, n):
		li = []
		for letter in w:
			if letter not in x:
				li.append(ord(letter))
				continue
			li.append(b[x.index(letter)])
		max_so_far = float('-inf')
		max_ending = 0
		t = ''
		st = 0
		s = 0
		en = 0
		for i in range(0, len(li)):
			max_ending = max_ending + li[i]
			t = t + w[i]
			if max_ending > max_so_far:
				max_so_far = max_ending
				st = s
				en = i
			if max_ending < 0:
				max_ending = 0
				s = i + 1
		return w[st:en + 1]


class Solution:

	def maxSum(self, w, x, b, n):

		def helper(char):
			if char in x:
				return b[x.index(char)]
			return ord(char)
		total = 0
		(ml, mr, l, r) = (0, 0, 0, 0)
		Max = float('-inf')
		for i in range(len(w)):
			curval = helper(w[i])
			if curval > curval + total:
				total = curval
				l = i
				r = i
			else:
				total += curval
				r = i
			if total > Max:
				Max = total
				ml = l
				mr = r
		return w[ml:mr + 1]


class Solution:

	def maxSum(self, w, x, b, n):
		d = {}
		s = float('-inf')
		ans = float('-inf')
		for i in range(n):
			d[x[i]] = b[i]
		x = 0
		res = [-1, -1]
		for i in range(len(w)):
			if w[i] in d:
				val = d[w[i]]
			else:
				val = ord(w[i])
			if s + val < val:
				j = i
				s = val
			else:
				s += val
			if ans < s:
				res[0] = j
				res[1] = i
				ans = s
		return w[res[0]:res[1] + 1]


class Solution:

	def maxSum(self, w, x, b, n):
		cur_max = 0
		overall_max = -100000000
		cur_string = ''
		overall_string = ''
		for c in w:
			n = ord(c) if c not in x else b[x.index(c)]
			cur_max += n
			cur_string += c
			if cur_max > overall_max:
				overall_max = cur_max
				overall_string = cur_string
			if cur_max < 0:
				cur_max = 0
				cur_string = ''
		return overall_string


class Solution:

	def maxSum(self, w, x, b, n):
		res = ''
		raji = ''
		curr = 0
		maxi = -float('infinity')
		for (a, i) in enumerate(w):
			p = ord(i)
			if i in x:
				p = b[x.index(i)]
			curr += p
			raji += i
			if curr > maxi:
				maxi = curr
				res = raji
			if curr < 0:
				curr = 0
				raji = ''
		return res


class Solution:

	def maxSum(self, w, x, b, n):
		chr_arr = []
		hashmap = dict(zip(x, b))
		for i in w:
			if i in hashmap:
				chr_arr.append(hashmap[i])
				continue
			chr_arr.append(ord(i))
		localmax = globalmax = chr_arr[0]
		t_begin = t_end = g_begin = g_end = 0
		for i in range(1, len(chr_arr)):
			if chr_arr[i] < chr_arr[i] + localmax or localmax == 0:
				localmax = chr_arr[i] + localmax
				t_end = i
			else:
				localmax = chr_arr[i]
				t_begin = i
				t_end = i
			if localmax > globalmax:
				globalmax = localmax
				g_begin = t_begin
				g_end = t_end
		return w[g_begin:g_end + 1]


class Solution:

	def maxSum(self, w, x, b, n):
		map = {}
		for i in range(n):
			map[x[i]] = b[i]
		maxi = float('-inf')
		ans = ''
		temp = ''
		sum = 0
		i = 0
		while i < len(w):
			if w[i] in map:
				sum = sum + map[w[i]]
			else:
				sum = sum + ord(w[i])
			temp = temp + w[i]
			i += 1
			if sum > maxi:
				maxi = sum
				ans = temp
			if sum < 0:
				sum = 0
				temp = ''
		return ans


from sys import maxsize

class Solution:

	def maxSum(self, w, x, b, n):
		arr = []
		for i in w:
			if i in x:
				ind = x.index(i)
				arr.append(b[ind])
			else:
				arr.append(ord(i))
		current_sum = max_sum = arr[0]
		if len(arr) == 0:
			return 0
		max_so_far = -maxsize - 1
		max_ending_here = 0
		start = end = s = 0
		for i in range(0, len(arr)):
			max_ending_here += arr[i]
			if max_so_far < max_ending_here:
				max_so_far = max_ending_here
				start = s
				end = i
			if max_ending_here < 0:
				max_ending_here = 0
				s = i + 1
		return w[start:end + 1]


class Solution:

	def maxSum(self, w, x, b, n):
		result = -float('inf')
		temp = 0
		(u, v) = (0, 0)
		(i, j) = (0, 0)
		for c in range(len(w)):
			for k in range(n):
				if w[c] == x[k]:
					temp += b[k]
					break
			else:
				temp += ord(w[c])
			j += 1
			if temp >= result:
				(u, v) = (i, j)
				result = temp
			if temp < 0:
				temp = 0
				i = c + 1
				j = c + 1
		return w[u:v]


class Solution:

	def maxSum(self, w, x, b, n):
		max_sum_here = 0
		max_sum_whole = max_sum_here
		start = end = s = 0
		for i in range(0, len(w)):
			if w[i] not in x:
				if ord(w[i]) + max_sum_here >= 0:
					max_sum_here += ord(w[i])
					if max_sum_here >= max_sum_whole:
						max_sum_whole = max_sum_here
						start = s
						end = i
			elif b[x.index(w[i])] + max_sum_here >= 0:
				max_sum_here += b[x.index(w[i])]
				if max_sum_here >= max_sum_whole:
					max_sum_whole = max_sum_here
					start = s
					end = i
			else:
				s = i + 1
				max_sum_here = 0
		return w[start:end + 1]


class Solution:

	def maxSum(self, w, x, b, n):
		char_weight = {ch: wt for (ch, wt) in zip(x, b)}
		(res, temp) = ('', '')
		(res_sum, curr_sum) = (float('-inf'), 0)
		for ch in w:
			val = ord(ch) if ch not in char_weight else char_weight[ch]
			if val <= curr_sum + val:
				curr_sum += val
				temp += ch
			else:
				curr_sum = val
				temp = ch
			if curr_sum > res_sum:
				res_sum = curr_sum
				res = temp
		return res


class Solution:

	def maxSum(self, w, x, b, n):
		s = set(w)
		asci = {}
		for i in s:
			if i in x:
				asci[i] = b[x.index(i)]
			else:
				asci[i] = ord(i)
		curr_max = 0
		max_so_far = float('-inf')
		N = len(w)
		s = 0
		e = 0
		start = 0
		for i in range(N):
			curr_max += asci[w[i]]
			if max_so_far < curr_max:
				max_so_far = curr_max
				s = start
				e = i
			if curr_max < 0:
				curr_max = 0
				if i + 1 < N:
					start = i + 1
		return w[s:e + 1]


class Solution:

	def maxSum(self, w, x, b, n):
		d = dict()
		for i in range(len(x)):
			d[x[i]] = b[i]
		s = 0
		l = 0
		m = -99999
		for i in range(len(w)):
			if w[i] not in d:
				s += ord(w[i])
			else:
				s += d[w[i]]
			if s > m:
				ans = w[l:i + 1]
				m = s
			if s < 0:
				s = 0
				l = i + 1
		return ans


class Solution:

	def maxSum(self, w, x, b, n):
		score = {}
		for i in range(97, 97 + 26):
			score[chr(i)] = i
		for i in range(65, 65 + 26):
			score[chr(i)] = i
		for i in range(n):
			score[x[i]] = b[i]
		n = len(w)
		s = 0
		m = [0, 0]
		ans = [0, 1, score[w[0]]]
		for i in range(n):
			s += score[w[i]]
			if s - m[0] > ans[2]:
				ans[0] = m[1]
				ans[1] = i + 1
				ans[2] = s - m[0]
			if s < m[0]:
				m = [s, i + 1]
		return w[ans[0]:ans[1]]


class Solution:

	def maxSum(self, w, x, b, n):
		d = {}
		for i in range(n):
			d[x[i]] = b[i]
		arr = []
		for i in w:
			if i in d:
				arr.append(d[i])
			else:
				arr.append(ord(i))
		if len(arr) == 1:
			return w
		m = 0
		res = 0
		s = ''
		ans = ''
		for i in range(len(arr)):
			m = max(arr[i], m + arr[i])
			if m < 0:
				s = ''
				continue
			s += w[i]
			if m >= res:
				res = m
				ans = s
		if len(ans) == 0:
			m = arr[0]
			res = arr[0]
			ans = w[0]
			for i in range(1, len(arr)):
				m = max(arr[i], m)
				if m > res:
					res = m
					ans = w[i]
		return ans


class Solution:

	def maxSum(self, w, x, b, n):
		eval_char = lambda a: b[x.index(a)] if a in x else ord(a)
		len_w = len(w)
		max_i = i = 0
		max_j = j = 0
		max_sum = summ = eval_char(w[j])
		while j < len_w - 1:
			if summ < 0:
				j += 1
				i = j
				summ = eval_char(w[i])
			else:
				j += 1
				summ += eval_char(w[j])
			if summ > max_sum:
				max_sum = summ
				max_i = i
				max_j = j
		return w[max_i:max_j + 1]


class Solution:

	def maxSum(self, w, x, b, n):
		eval_char = lambda a: b[x.index(a)] if a in x else ord(a)
		len_w = len(w)
		i = 0
		j = 0
		max_str = w[j]
		max_sum = summ = eval_char(w[j])
		while j < len_w - 1:
			if i < j and i < 0:
				summ -= eval_char(w[i])
				i += 1
			elif summ < 0:
				j += 1
				i = j
				summ = eval_char(w[i])
			else:
				j += 1
				summ += eval_char(w[j])
			if summ > max_sum:
				max_sum = summ
				max_str = w[i:j + 1]
		return max_str


from string import ascii_lowercase, ascii_uppercase

class Solution:

	def maxSum(self, w, x, b, n):
		if len(w) == 1:
			return w
		m = {}
		for c in ascii_lowercase + ascii_uppercase:
			m[c] = ord(c)
		m.update(zip(x, b))
		localmax = globalmax = float('-inf')
		ans = None
		i = j = 0
		for (index, c) in enumerate(w):
			newlocalmax1 = localmax + m[c]
			newlocalmax2 = m[c]
			if newlocalmax1 >= newlocalmax2:
				localmax = newlocalmax1
				j = index
			else:
				localmax = newlocalmax2
				i = j = index
			if globalmax < localmax:
				globalmax = localmax
				ans = (i, j)
		return w[ans[0]:ans[1] + 1]


class Solution:

	def maxSum(self, w, x, b, n):
		res = 0
		res1 = 0
		string_res = ''
		string_res1 = ''
		store = {}
		value = {}
		if len(w) == 1:
			return w[0]
		for i in range(n):
			value[x[i]] = b[i]
		curent = 0
		maxtilnow = 0
		rangeindex = 0
		startindex = 0
		endindex = 0
		answer = ''
		storkeys = [a for a in store.keys()]
		storvalue = list((b for b in store.values()))
		for i in range(len(w)):
			curent += ord(w[i]) if w[i] not in value else value[w[i]]
			if curent < 0:
				curent = 0
				rangeindex = i + 1
			elif curent > maxtilnow:
				maxtilnow = curent
				startindex = rangeindex
				endindex = i
		for i in range(startindex, endindex + 1):
			answer += w[i]
		return answer


class Solution:

	def maxSum(self, w, x, b, n):
		map = {}
		for i in range(len(x)):
			map[x[i]] = b[i]
		res = -1e+19
		result = ''
		curr = 0
		s = ''
		for i in w:
			if curr < 0:
				curr = 0
				s = ''
			if i in map:
				curr += map[i]
			else:
				curr += ord(i)
			s += i
			if res < curr:
				res = curr
				result = s
		return result


class Solution:

	def maxSum(self, w, x, b, n):
		ms = -1000000
		cs = 0
		ans = ''
		t = ''
		d = {}
		for i in range(n):
			d[x[i]] = b[i]
		for j in range(len(w)):
			ans += w[j]
			if w[j] not in d:
				cs += ord(w[j])
			else:
				cs += d[w[j]]
			if cs > ms:
				ms = cs
				t = ans
			if cs < 0:
				cs = 0
				ans = ''
		return t


get_ascii = lambda c, asciidict: asciidict.get(c, ord(c))

class Solution:

	def maxSum(self, w, x, b, n):
		asciidict = {x[i]: b[i] for i in range(n)}
		(s_i, e_i, cur_s) = (0, 0, 0)
		max_sum = 0
		cursum = 0
		for (idx, c) in enumerate(w):
			cursum = cursum + get_ascii(c, asciidict)
			if cursum < 0:
				cur_s = idx + 1
				cursum = 0
			elif cursum < max_sum:
				continue
			elif cursum >= max_sum:
				max_sum = cursum
				s_i = cur_s
				e_i = idx
		return w[s_i:e_i + 1]