Lexicographically Smallest String After Operations With Constraint

Lexicographically Smallest String After Operations With Constraint - Problem

String Greedy Medium

You are given a string s and an integer k. Define a function distance(s1, s2) between two strings s1 and s2 of the same length n as:

The sum of the minimum distance between s1[i] and s2[i] when the characters from 'a' to 'z' are placed in a cyclic order, for all i in the range [0, n - 1].

For example, distance("ab", "cd") == 4, and distance("a", "z") == 1.

You can change any letter of s to any other lowercase English letter, any number of times.

Return a string denoting the lexicographically smallest string t you can get after some changes, such that distance(s, t) <= k.

Input & Output

Example 1 — Basic Transformation

$ Input: s = "zab", k = 2

› Output: "aaa"

💡 Note: Change 'z' to 'a' (cost 1), 'a' stays 'a' (cost 0), change 'b' to 'a' (cost 1). Total cost = 2 ≤ k.

Example 2 — Limited Budget

$ Input: s = "xkcd", k = 4

› Output: "aakd"

💡 Note: Change 'x' to 'a' (cost 3), change 'k' to 'a' (cost 10, too expensive) → 'k' stays, 'c' stays, 'd' stays. Only 1 budget left.

Example 3 — Insufficient Budget

$ Input: s = "abc", k = 0

› Output: "abc"

💡 Note: No budget available, string remains unchanged.

Constraints

1 ≤ s.length ≤ 10⁵
0 ≤ k ≤ 2 × 10⁵
s consists of lowercase English letters only

Visualization

Tap to expand

Understanding the Visualization

Input

String "zab" with budget k=2

Process

Greedily transform each character to 'a' if budget allows

Output

Result "aaa" with total distance 2

Key Takeaway

🎯 Key Insight: Process characters left-to-right, always prioritizing 'a' to achieve lexicographically smallest string

Asked in

G Google 25 a Amazon 18 M Microsoft 15 f Meta 12

The key insight is to use a greedy approach, processing characters from left to right and always trying to use 'a' first for lexicographically smallest result. The optimal approach is greedy transformation with Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Combinations	O(26ⁿ × n)	O(n)	Generate all possible strings and find the lexicographically smallest one within distance k
Greedy Approach	O(n)	O(1)	Process characters left-to-right, greedily changing each to the smallest possible character

Brute Force - Try All Combinations — Algorithm Steps

Generate all possible strings of length n
Calculate distance for each string
Filter strings with distance <= k
Return lexicographically smallest valid string

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate

Create all possible strings of same length

Filter

Keep only strings with distance <= k

Select

Return lexicographically smallest

Code -

solution.c — C

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

int getDistance(char c1, char c2) {
    int diff = abs(c1 - c2);
    return (diff > 13) ? 26 - diff : diff;
}

int calculateTotalDistance(const char* s1, const char* s2) {
    int total = 0;
    int len = strlen(s1);
    for (int i = 0; i < len; i++) {
        total += getDistance(s1[i], s2[i]);
    }
    return total;
}

char* solution(char* s, int k) {
    int n = strlen(s);
    char* result = (char*)malloc((n + 1) * sizeof(char));
    strcpy(result, s);
    
    // For brute force, we'll implement a simplified version
    // that tries to optimize greedily due to complexity constraints
    for (int i = 0; i < n; i++) {
        char bestChar = s[i];
        int bestDistance = calculateTotalDistance(s, result);
        
        for (char c = 'a'; c <= 'z'; c++) {
            char temp = result[i];
            result[i] = c;
            int dist = calculateTotalDistance(s, result);
            
            if (dist <= k && (c < bestChar || bestDistance > k)) {
                bestChar = c;
                bestDistance = dist;
            }
            result[i] = temp;
        }
        result[i] = bestChar;
    }
    
    return result;
}

int main() {
    char s[1001];
    int k;
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    scanf("%d", &k);
    
    char* result = solution(s, k);
    printf("%s\n", result);
    free(result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(26ⁿ × n)

Generate 26^n possible strings, each taking O(n) time to calculate distance

✓ Linear Growth

Space Complexity

O(n)

Store result string and temporary strings during generation

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~15 min Avg. Time

856 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 Combinations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler