This content originally appeared on DEV Community and was authored by Manasi Patil

Taking on a new challenge: solving GeeksforGeeks POTD daily and sharing my solutions!
The goal: sharpen problem-solving skills, level up coding, and learn something new every day. Follow my journey!

100DaysOfCode #CodingChallenge #ProblemSolving #GeeksforGeeks #DeveloperJourney

Problem:

https://www.geeksforgeeks.org/problems/maximise-string-score–172902/1

Maximise String Score

Difficulty: Medium Accuracy: 51.27%

You are given a string s, and a list of jumps[][] of size n, where each jumps[i] = [s1, s2] denotes that you are allowed to jump from character s1 to s2 in the forward direction.
Additionally, you are allowed to jump forward from a character to any other occurrence of the same character within the string.
You start at index 0 of the string. After every valid jump from index i to index j, where s[i] = s1 and s[j] = s2, you earn a score equal to the sum of ASCII values of all characters between the jump except for the characters equals s2, i.e.
score(i, j) = sum(ascii(s[k]) for i ≤ k < j and s[k] != s[j]).
Determine the maximum score that can be achieved by performing a sequence of valid jumps starting from index 0.

Examples:
Input: s = “forgfg”, jumps[][] = [[‘f’, ‘r’], [‘r’, ‘g’]]
Output: 429
Explanation: We can jump from ‘f’ to ‘r’ at index 2, this will gives a score equals to sum of ASCII value of ‘f’, ‘o’ i.e. 213.
Now we can jump from ‘r’ to ‘g’ at index 5, this will gives a score equals to sum of ASCII value of ‘r’, ‘f’ i.e. 216.
Hence maximum total score obtain will be 429.
Input: s = “abcda”, jumps[][] = [[b, d]]
Output: 297
Explanation: We can jump from ‘a’ to ‘a'(as both are same character) at index 4, this will gives a score equals to sum of ASCII value of ‘b’, ‘c’, ‘d’ i.e. 297.
Hence maximum total score obtain will be 297.
Constraints:
1 ≤ |s| ≤ 2 * 105
1 ≤ jumps.size() ≤ 676
There are atleast two distinct characters in s.

Solution:
from itertools import accumulate
from collections import defaultdict
class Solution:

def maxScore(self, s, jumps):

    prefix_sum = list(accumulate(map(ord, s), initial=0))
    graph = defaultdict(set) 
    for u, v in jumps:
        graph[u].add(v) 
    for ch in set(s):
        graph[ch].add(ch) 

    lookup = [[-1]*26 for _ in range(len(s))]
    last_idx = [-1]*26 
    for i in range(len(s)-1, -1, -1):
        for j in range(26):
            lookup[i][j] = last_idx[j] 
        last_idx[ord(s[i])-ord('a')] = i 

    dp = [0]*len(s)

    for i in range(len(s)-2, -1, -1):
        for ch in graph[s[i]]:
            nxt_pos = lookup[i][ord(ch)-ord('a')] 
            if nxt_pos == -1:
                continue 
            if ch == s[i]:
                dp[i] = max(dp[i], dp[nxt_pos] + prefix_sum[nxt_pos] - prefix_sum[i+1])
            else:
                dp[i] = max(dp[i], dp[nxt_pos] + prefix_sum[nxt_pos] - prefix_sum[i])
    return dp[0]

This content originally appeared on DEV Community and was authored by Manasi Patil