Minimum Cost Good Caption

Minimum Cost Good Caption - Problem

You're working on a social media platform that validates captions for posts. A good caption is one where every character appears in groups of at least 3 consecutive occurrences.

Examples:

"aaabbb" ✅ Good caption (3 a's, 3 b's)
"aaaaccc" ✅ Good caption (4 a's, 3 c's)
"aabbb" ❌ Bad caption (only 2 a's)
"ccccd" ❌ Bad caption (only 1 d)

You can modify any character by changing it to an adjacent alphabet character:

Change to previous character (e.g., 'b' → 'a'), unless it's 'a'
Change to next character (e.g., 'b' → 'c'), unless it's 'z'

Goal: Transform the caption into a good caption using the minimum number of operations. If multiple solutions exist, return the lexicographically smallest one. If impossible, return an empty string.

Input & Output

example_1.py — Basic Transformation

$ Input: "aabcc"

› Output: "aaabbb"

💡 Note: Change the last 'c' to 'b' (cost 1) and the second-to-last 'c' to 'b' (cost 1). Total cost: 2. Result: "aaabbb" with groups of 3 a's and 3 b's.

example_2.py — Lexicographically Smallest

$ Input: "abc"

› Output: "aaa"

💡 Note: Transform all characters to 'a': change 'b' to 'a' (cost 1) and 'c' to 'b' to 'a' (cost 2). Total cost: 3. "aaa" is lexicographically smaller than "bbb" or "ccc".

example_3.py — Impossible Case

$ Input: "az"

› Output: ""

💡 Note: String length is 2, which is less than 3. Cannot form any groups of 3+ consecutive characters. Return empty string.

Constraints

1 ≤ caption.length ≤ 1000
caption consists of only lowercase English letters
Each group must have at least 3 consecutive identical characters
Return lexicographically smallest result among minimum cost solutions

Visualization

Tap to expand

Asked in

G Google 23 f Meta 18 a Amazon 15 ⊞ Microsoft 12

The optimal approach uses Dynamic Programming to find the minimum cost transformation. Key insights: (1) Segment the string optimally where each segment becomes a group of identical characters, (2) Each segment must have length ≥ 3, (3) Use DP to build solutions incrementally, considering all possible segmentations, (4) For lexicographic ordering, prefer smaller characters when costs are equal.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force (Try All Combinations)	O(3^n)	O(n)	Try every possible character change combination recursively
Dynamic Programming with Memoization	O(n³)	O(n²)	Use DP to find optimal segmentation and character assignments

Brute Force (Try All Combinations) — Algorithm Steps

For each position, try keeping the character or changing it to adjacent characters
Recursively generate all possible combinations
Check each combination if it forms a good caption
Track the minimum cost solution that is lexicographically smallest

Visualization

Tap to expand

Step-by-Step Walkthrough

Start at root

Begin with original string

Branch at each position

Try keep, increment, decrement for each character

Evaluate leaves

Check if resulting string is good caption

Track minimum

Keep track of minimum cost valid solution

Code -

solution.c — C

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

int minCost = INT_MAX;
char bestResult[1001];

int isGoodCaption(char* s) {
    int len = strlen(s);
    if (len == 0) return 0;
    
    int i = 0;
    while (i < len) {
        int count = 1;
        while (i + count < len && s[i + count] == s[i]) {
            count++;
        }
        if (count < 3) return 0;
        i += count;
    }
    return 1;
}

void backtrack(char* caption, int pos, char* current, int cost, int n) {
    if (pos == n) {
        if (isGoodCaption(current)) {
            if (cost < minCost || (cost == minCost && strcmp(current, bestResult) < 0)) {
                minCost = cost;
                strcpy(bestResult, current);
            }
        }
        return;
    }
    
    char ch = caption[pos];
    int currentLen = strlen(current);
    
    // Keep current character
    current[currentLen] = ch;
    current[currentLen + 1] = '\0';
    backtrack(caption, pos + 1, current, cost, n);
    current[currentLen] = '\0';
    
    // Try previous character
    if (ch != 'a') {
        current[currentLen] = ch - 1;
        current[currentLen + 1] = '\0';
        backtrack(caption, pos + 1, current, cost + 1, n);
        current[currentLen] = '\0';
    }
    
    // Try next character
    if (ch != 'z') {
        current[currentLen] = ch + 1;
        current[currentLen + 1] = '\0';
        backtrack(caption, pos + 1, current, cost + 1, n);
        current[currentLen] = '\0';
    }
}

char* minimumCostGoodCaption(char* caption) {
    int n = strlen(caption);
    if (n == 0) return "";
    
    minCost = INT_MAX;
    strcpy(bestResult, "");
    
    char current[1001] = "";
    backtrack(caption, 0, current, 0, n);
    
    return bestResult;
}

int main() {
    char caption[1001];
    fgets(caption, sizeof(caption), stdin);
    
    // Remove newline and quotes
    caption[strcspn(caption, "\n")] = 0;
    if (caption[0] == '"') {
        memmove(caption, caption + 1, strlen(caption));
    }
    if (caption[strlen(caption) - 1] == '"') {
        caption[strlen(caption) - 1] = '\0';
    }
    
    char* result = minimumCostGoodCaption(caption);
    printf("\"%s\"", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(3^n)

For each position, we have 3 choices (keep, increment, decrement), leading to exponential combinations

✓ Linear Growth

Space Complexity

O(n)

Recursion stack depth plus space to store the current string being built

⚡ Linearithmic Space

26.2K Views

Medium Frequency

~35 min Avg. Time

847 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