Largest Number After Mutating Substring - Practice Coding Problems

Largest Number After Mutating Substring - Problem

You are given a string num, which represents a large integer. You are also given a 0-indexed integer array change of length 10 that maps each digit 0-9 to another digit. More formally, digit d maps to digit change[d].

You may choose to mutate a single substring of num. To mutate a substring, replace each digit num[i] with the digit it maps to in change (i.e. replace num[i] with change[num[i]]).

Return a string representing the largest possible integer after mutating (or choosing not to) a single substring of num.

A substring is a contiguous sequence of characters within the string.

Input & Output

Example 1 — Basic Transformation

$ Input: num = "132", change = [9,8,5,0,2,6,7,1,4,3]

› Output: "855"

💡 Note: Start at position 0: 1→8 (improvement), continue: 3→5 (improvement), 2→5 (improvement). Result: "855"

Example 2 — No Improvement Possible

$ Input: num = "021", change = [9,8,5,0,2,6,7,1,4,3]

› Output: "021"

💡 Note: 0→9 would be improvement but we can't change leading 0s to make number larger lexicographically. Other digits: 2→5, 1→8 would help but starting with 0 limits us.

Example 3 — Partial Transformation

$ Input: num = "5", change = [1,4,7,5,2,6,9,3,0,8]

› Output: "5"

💡 Note: 5→2 would make it smaller, so no transformation gives the best result

Constraints

1 ≤ num.length ≤ 10⁵
num consists of only digits 0-9
change.length == 10
0 ≤ change[i] ≤ 9

Visualization

Tap to expand

Understanding the Visualization

Input

String num="132" and change array [9,8,5,0,2,6,7,1,4,3]

Transform

Apply optimal substring mutation: 1→8, 3→5, 2→5

Output

Largest possible number: "855"

Key Takeaway

🎯 Key Insight: Greedily transform from the first improvable digit, continuing while beneficial

Asked in

G Google 25 a Amazon 20 M Microsoft 15

The key insight is to use a greedy approach: find the first digit that can be improved, then continue transforming consecutive digits while beneficial. This ensures we get the lexicographically largest result. Best approach is greedy single-pass. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Substrings	O(n³)	O(n)	Generate all possible substrings, transform each, and find the maximum
Greedy Approach	O(n)	O(n)	Find first improvable digit, transform consecutive beneficial digits

Brute Force - Try All Substrings — Algorithm Steps

Iterate through all possible starting positions
For each start, try all possible ending positions
Transform the substring and compare with current maximum

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Substrings

Create all possible contiguous substrings

Transform Each

Apply digit mapping to each substring

Find Maximum

Compare all results to find largest number

Code -

solution.c — C

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

char* solution(char* num, int* change) {
    int n = strlen(num);
    char* maxResult = malloc((n + 1) * sizeof(char));
    strcpy(maxResult, num);
    
    // Try all possible substrings
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            // Transform substring from i to j
            char* transformed = malloc((n + 1) * sizeof(char));
            strcpy(transformed, num);
            
            for (int k = i; k <= j; k++) {
                int digit = transformed[k] - '0';
                transformed[k] = change[digit] + '0';
            }
            
            if (strcmp(transformed, maxResult) > 0) {
                strcpy(maxResult, transformed);
            }
            
            free(transformed);
        }
    }
    
    return maxResult;
}

int main() {
    char num[100001];
    fgets(num, sizeof(num), stdin);
    num[strcspn(num, "\n")] = 0;
    
    char changeLine[100];
    fgets(changeLine, sizeof(changeLine), stdin);
    
    // Parse array manually
    int change[10];
    char* token = strtok(changeLine + 1, ",]");
    int i = 0;
    while (token && i < 10) {
        change[i++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    char* result = solution(num, change);
    printf("%s\n", result);
    free(result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

O(n²) substrings, each taking O(n) time to process and compare

⚠ Quadratic Growth

Space Complexity

O(n)

String creation for each substring transformation

⚡ Linearithmic Space

32.0K Views

Medium Frequency

~25 min Avg. Time

890 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 - Try All Substrings — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler