Find the Substring With Maximum Cost - Practice Coding Problems

Find the Substring With Maximum Cost - Problem

You are given a string s, a string chars of distinct characters, and an integer array vals of the same length as chars.

The cost of the substring is the sum of the values of each character in the substring. The cost of an empty string is considered 0.

The value of the character is defined in the following way:

If the character is not in the string chars, then its value is its corresponding position (1-indexed) in the alphabet.
- For example, the value of 'a' is 1, the value of 'b' is 2, and so on. The value of 'z' is 26.
Otherwise, assuming i is the index where the character occurs in the string chars, then its value is vals[i].

Return the maximum cost among all substrings of the string s.

Input & Output

Example 1 — Basic Case

$ Input: s = "adaa", chars = "d", vals = [-1000]

› Output: 2

💡 Note: Character 'd' has value -1000, others use alphabet positions: 'a'=1. Best substring is "aa" at the end with cost 1+1=2.

Example 2 — All Custom Values

$ Input: s = "abc", chars = "abc", vals = [-1,-1,1]

› Output: 1

💡 Note: All characters have custom values: 'a'=-1, 'b'=-1, 'c'=1. Best substring is "c" with cost 1.

Example 3 — Empty Substring Optimal

$ Input: s = "z", chars = "z", vals = [-100]

› Output: 0

💡 Note: Character 'z' has value -100, which is negative. Empty substring has cost 0, which is better.

Constraints

1 ≤ s.length ≤ 10⁵
0 ≤ chars.length ≤ 26
chars.length = vals.length
1 ≤ vals[i] ≤ 2000
s and chars consist of lowercase English letters
All characters in chars are distinct

Visualization

Tap to expand

Understanding the Visualization

Input

String s with custom character values

Transform

Convert characters to their corresponding values

Apply Kadane's

Find maximum sum contiguous subarray

Key Takeaway

🎯 Key Insight: Convert string to values array, then use Kadane's algorithm for maximum subarray sum

Asked in

G Google 12 F Facebook 8 A Amazon 15 M Microsoft 6

This problem transforms a substring cost calculation into a maximum subarray problem. The key insight is to first map each character to its value (custom or alphabet position), then apply Kadane's algorithm to find the maximum sum of any contiguous subarray. The optimal solution runs in O(n) time with O(1) space.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O(n³)	O(1)	Check all possible substrings and calculate their costs
Kadane's Algorithm (Optimal)	O(n)	O(1)	Transform to character values array, then apply Kadane's algorithm

Brute Force — Algorithm Steps

Create character value mapping
Generate all substrings
Calculate cost for each substring
Return maximum cost

Visualization

Tap to expand

Step-by-Step Walkthrough

Create Mapping

Map special characters to their custom values

Generate Substrings

Check all possible substrings one by one

Calculate Costs

Sum character values for each substring and track maximum

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(char* s, char* chars, int* vals, int valsSize) {
    int maxCost = 0;
    int n = strlen(s);
    
    // Check all possible substrings
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            int cost = 0;
            for (int k = i; k <= j; k++) {
                char c = s[k];
                int value = c - 'a' + 1; // default value
                
                // Check if character is in chars
                for (int l = 0; l < strlen(chars); l++) {
                    if (chars[l] == c) {
                        value = vals[l];
                        break;
                    }
                }
                cost += value;
            }
            if (cost > maxCost) {
                maxCost = cost;
            }
        }
    }
    
    return maxCost;
}

int main() {
    char s[1001], chars[27], valsStr[1001];
    fgets(s, sizeof(s), stdin);
    fgets(chars, sizeof(chars), stdin);
    fgets(valsStr, sizeof(valsStr), stdin);
    
    // Remove newlines
    s[strcspn(s, "\n")] = 0;
    chars[strcspn(chars, "\n")] = 0;
    valsStr[strcspn(valsStr, "\n")] = 0;
    
    // Parse vals array
    int vals[26];
    int valsSize = 0;
    char* token = strtok(valsStr + 1, ",]");
    while (token != NULL) {
        vals[valsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int result = solution(s, chars, vals, valsSize);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

O(n²) substrings, each taking O(n) time to calculate cost

⚠ Quadratic Growth

Space Complexity

O(1)

Only using constant extra space for variables

✓ Linear Space

23.5K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler