Problem1 Solution -: 

Sum of Palindromic Substrings Weight Solution

Topics Involved / Prerequisites

• Two Pointers (Expand Around Center)

Overview

1. We need to identify every valid palindromic substring and calculate its alphabetical weight.
2. Instead of checking every possible substring from scratch, we can treat each character as a center and expand outwards to find valid palindromes efficiently.
3. By using a prefix sum array to instantly calculate weights and applying the modulo operation at each step, we keep the solution fast and prevent integer overflow.

Approach

1. Fast Weight Calculation (Prefix Sums)

Calculating the alphabetical weight of a substring repeatedly by looping through its characters is too slow. Instead, we can create a prefixWeight array. By converting each character into its weight (a=1, b=2, .. ) and keeping a running total, we can find the weight of any substring in O(1) constant time by simply subtracting the prefix value before the start index from the prefix value at the end index.

2. Expand Around Center

A palindrome mirrors around its center. There are (2N - 1) possible centers in a string (each character is a center for odd-length palindromes, and the space between each pair of adjacent characters is a center for even-length palindromes). We loop through all possible centers, expand our left and right pointers outward as long as the characters match, and add the O(1) substring weight to our total sum.

function getCharWeight(c):
    return ASCII(c) - ASCII('a') + 1

function sumOfPalindromicWeights(s):
    MOD = 1000000007
    n = length of s
    totalSum = 0
    

    for i from 0 to n - 1:
        prefixWeight[i + 1] = prefixWeight[i] + getCharWeight(s[i])
        

    function expandAndSum(left, right):
        localSum = 0
        while left >= 0 AND right < n AND s[left] == s[right]:
            // Calculate weight using the prefix sum array
            weight = prefixWeight[right + 1] - prefixWeight[left]
            localSum = (localSum + weight) % MOD
            
            // Expand outwards
            left = left - 1
            right = right + 1
            
        return localSum


    for i from 0 to n - 1:
        // Odd length palindromes (centered on character i)
        totalSum = (totalSum + expandAndSum(i, i)) % MOD
        
        // Even length palindromes (centered between i and i + 1)
        totalSum = (totalSum + expandAndSum(i, i + 1)) % MOD
        
    return totalSum

Time Complexity

• Time: O(N^2) - In the worst case (e.g., a string of all the same characters like "aaaa"), the pointers will expand O(N) times for each of the O(N) centers.
• Space: O(N) - For storing the prefixWeight array.

Problem2 Solution

Wallet Transactions (SQL) Solution

Overview

We need to fetch wallet addresses but strictly filter for those wallets that have actively participated in at least one transaction.

Using an INNER JOIN seamlessly connects the two tables, while the DISTINCT keyword ensures we don't output the same wallet address multiple times.

Sorting the final result alphabetically with ORDER BY ensures the output matches the required formatting constraints.

Approach

1. Connecting the Tables

We only care about wallets that have a corresponding entry in the transactions table. An INNER JOIN on the wallet_id perfectly acts as a filter, automatically dropping any wallets from our result set that have zero transactions.

2. Removing Duplicates and Sorting

If a wallet has made five transactions, the INNER JOIN will initially generate five rows for that wallet address. By selecting DISTINCT w.address, we collapse those duplicates down to a single row. Finally, we append ORDER BY w.address ASC to sort them alphabetically.

SELECT DISTINCT w.address
FROM wallets w
INNER JOIN transactions t 
    ON w.id = t.wallet_id
ORDER BY 
    w.address ASC;