Decremental String Concatenation - Practice Coding Problems

Decremental String Concatenation - Problem

You are given a 0-indexed array words containing n strings.

Let's define a join operation join(x, y) between two strings x and y as concatenating them into xy. However, if the last character of x is equal to the first character of y, one of them is deleted.

For example: join("ab", "ba") = "aba" and join("ab", "cde") = "abcde".

You are to perform n - 1 join operations. Let str0 = words[0]. Starting from i = 1 up to i = n - 1, for the ith operation, you can do one of the following:

Make stri = join(stri - 1, words[i])
Make stri = join(words[i], stri - 1)

Your task is to minimize the length of strn - 1.

Return an integer denoting the minimum possible length of strn - 1.

Input & Output

Example 1 — Basic Case

$ Input: words = ["aa", "ab", "bc"]

› Output: 4

💡 Note: Join "aa" + "ab" = "aab" (no overlap), then "aab" + "bc" = "aabc" (b matches, one deleted) = length 4. Alternative: "aa" + "bc" + "ab" would give length 6, so 4 is optimal.

Example 2 — With Overlap

$ Input: words = ["ab", "ba"]

› Output: 3

💡 Note: join("ab", "ba") = "aba" because last char of "ab" (b) equals first char of "ba" (b), so one is deleted. Length = 3.

Example 3 — No Overlap

$ Input: words = ["abc", "def"]

› Output: 6

💡 Note: No characters match, so join("abc", "def") = "abcdef" with length 6. Order doesn't matter here.

Constraints

2 ≤ words.length ≤ 10
1 ≤ words[i].length ≤ 50
words[i] consists of lowercase English letters only

Visualization

Tap to expand

Understanding the Visualization

Input

Array of strings to join optimally

Join Process

Try both orders, save character if boundaries match

Output

Minimum possible length after all joins

Key Takeaway

🎯 Key Insight: Use DP to track optimal joins by monitoring string boundaries (first/last chars)

Asked in

G Google 15 M Microsoft 12 a Amazon 8

The key insight is to use dynamic programming with memoization, tracking the current position and the first/last characters of our accumulated string. This allows us to avoid recalculating the same subproblems. The optimal approach uses memoization with state (index, length, first_char, last_char). Time: O(n × 26²), Space: O(n × 26²)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Recursion	O(2ⁿ)	O(n)	Try all possible ways to join strings recursively
Dynamic Programming with Memoization	O(n × 26²)	O(n × 26²)	Optimize brute force by caching results based on current state

Brute Force Recursion — Algorithm Steps

Start with first string
For each remaining string, try both join orders
Recursively solve for remaining strings
Return minimum length found

Visualization

Tap to expand

Step-by-Step Walkthrough

Start

Begin with first string

Branch

Try both join orders for each string

Result

Find minimum length among all paths

Code -

solution.c — C

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

char* joinStrings(const char* x, const char* y) {
    int xLen = strlen(x);
    int yLen = strlen(y);
    
    char* result;
    if (xLen > 0 && yLen > 0 && x[xLen-1] == y[0]) {
        result = malloc(xLen + yLen);
        strcpy(result, x);
        strcat(result, y + 1);
    } else {
        result = malloc(xLen + yLen + 1);
        strcpy(result, x);
        strcat(result, y);
    }
    return result;
}

int backtrack(int index, const char* currentStr, char words[][101], int n) {
    if (index == n) {
        return strlen(currentStr);
    }
    
    char* joined1 = joinStrings(currentStr, words[index]);
    char* joined2 = joinStrings(words[index], currentStr);
    
    int option1 = backtrack(index + 1, joined1, words, n);
    int option2 = backtrack(index + 1, joined2, words, n);
    
    free(joined1);
    free(joined2);
    
    return option1 < option2 ? option1 : option2;
}

int solution(char words[][101], int n) {
    return backtrack(1, words[0], words, n);
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    char words[10][101];
    int n = 0;
    
    char* token = strtok(line + 1, ",]");
    while (token != NULL && n < 10) {
        while (*token == ' ' || *token == '"') token++;
        char* end = token + strlen(token) - 1;
        while (end > token && (*end == ' ' || *end == '"' || *end == '\n')) end--;
        *(end + 1) = '\0';
        strcpy(words[n], token);
        n++;
        token = strtok(NULL, ",]");
    }
    
    int result = solution(words, n);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2ⁿ)

Each of n-1 operations has 2 choices, leading to 2^(n-1) combinations

✓ Linear Growth

Space Complexity

O(n)

Recursion stack depth up to n levels

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~25 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 Recursion — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler